Антология предположений о сложности
В статье «Гипотеза случайного оракула ложна» авторы (Чанг, Чор, Гольдрайх, Хартманис, Хостад, Ранджан и Рохатхи) обсуждают значение гипотезы о случайном оракуле . Они утверждают, что мы очень мало знаем о разделениях между классами сложности, и большинство результатов включают либо использование...