Фон
Известно , что существует оракул такое , что .P S P A C E A ≠ P H A
Даже известно, что разделение справедливо относительно случайного оракула. Неофициально можно интерпретировать это как означающее, что существует много оракулов, для которых и разделены.P H
Вопрос
Насколько сложны эти оракулы, которые отделяют от . В частности, существует ли оракул такой, что ?P H A ∈ D T I M E ( 2 2 n ) P S P A C E A ≠ P H A
Есть ли у нас оракул такой, что и имеет верхнюю границу известной сложности?P S P A C E A ≠ P H A A
Примечание: существование такого оракула может иметь разветвления в теории структурной сложности. См. Следующее обновление ниже для получения дополнительной информации.
Обновление с подробной информацией о технике нижней границы
Утверждение: Если , то для всех оракулов , .A ∈ P / p o l y P S P A C E A = P H A
Эскиз доказательства: предположим, что .
Пусть дан оракул . Мы можем построить полиномиальное время оракула Тьюринг машина , что для заданной длины , угадывает схему размера с использованием экзистенциальной количественной оценки и проверяет , что схема принимает решение пути сравнения оценки схемы и результата запроса для каждой длины строки используется универсальное количественное определение.Σ 2 M n p ( n ) A n
Далее рассмотрим решение проблемы, которую я называю квантифицированной логической схемой (QBC), где вам дана квантифицированная логическая схема и вы хотите знать, действительна ли она (аналогично QBF). Эта проблема является PSPACE-полной, потому что QBF является PSPACE-полной.
По предположению следует, что QBC . Допустим, для некоторого достаточно большого размера. Пусть обозначает полиномиальное время машина Тьюринга, которая решает QBC.Q B C ∈ Σ k k N Σ k
Мы можем смешиваться вычисление и (подобно тому , как это делается при доказательстве теоремы Карп-Lipton) , чтобы получить полиномиальное время оракул машина Тьюринга , которая решает .N Σ k Q B C A
Неофициально, эта новая машина принимает в качестве входных данных оракула QBC (то есть QBC с воротами оракула). Затем он вычисляет схему, которая вычисляет на входах длины (одновременно удаляя первые два квантификатора). Далее, он заменяет оракула ворота в оракула QBC со схемой для . Наконец, он продолжает применять оставшуюся часть алгоритма полиномиального времени для решения на этом модифицированном экземпляре.n A Σ k Q B C
Теперь мы можем показать условную нижнюю границу.
Следствие: если существует оракул такой, что , то .P S P A C E A ≠ P H A N E X P ⊈ P / p o l y
Доказательство Sketch: Предположим , что существует такое , что . Если , мы получим противоречие.P S P A C E A ≠ P H A N E X P ⊆ P / p o l y
В частности, если , то согласно приведенному выше утверждению имеем . Однако известно, что подразумевает, что .Р С Р С Е ≠ Р Н Н Е Х Р ⊆ Р / р о л у P S P A C E = P H
(см. здесь некоторые подробности об известных результатах для P / poly)
Ответы:
Я полагаю, что если вы проследите аргумент, приведенный, например, в разделе 4.1 опроса Ker-I Ko , вы получите верхнюю границу . Фактически, мы можем заменить здесь любой функцией где как . Это не совсем то, о чем просили, но это близко.n 2 n f ( n ) f ( n ) → ∞ n → ∞DTIME(22O(n2)) n2 nf(n) f(n)→∞ n→∞
В частности, используя перевод между разделением оракула и нижними границами контура и следуя обозначениям Ко, мы имеем следующее:
Диагонализируем по строкам длины где - это « полином» (в некоторых перечислениях алгоритмов поли-времени) и будет указано ниже.p n ( x ) = x n + n n m ( n )t(n)=pn(m(n)) pn(x)=xn+n n m(n)
Переводя в нижние границы цепей, это означает, что мы рассматриваем схемы ограниченной глубины на входах.2t(n)
Требование (см. Стр. 15 Ко) нам нужно чтобы удовлетворить 1m(n) для всехn. Здесьd- глубина схем, против которых мы хотим диагонализировать, или, что эквивалентно, уровеньΣ p d вPH,против которого мы хотим диагонализировать. Чтобы диагонализировать всеPH, просто выберитеdкак функцию отn,то естьω(1); мы можем выбрать такойд1102m/(d−1)>dpn(m(n)) n d Σpd PH PH d n ω(1) d хотя он растет произвольно медленно (возможно, при условии некоторого предположения о вычислимости , но это не должно быть препятствием). Если мы предположим, что d ( n ) является постоянной величиной (хотя это не так, но она будет расти произвольно медленно), то мы увидим, что m ( n ) около 2 n должно работать.d(n) d(n) m(n) 2n
Это означает , что , поэтому мы ищем нижнюю границу от цепей с ~ 2 2 п 2 входами.t(n)∼2n2 ∼22n2
Тревисано и Сей (КТС '13) показали , что можно найти задание , на котором данный ограниченную глубину контур на входах не вычисляет соотношение с семени р ø л у л о г ( Н ) длиной.N polylog(N)
Для нас , поэтому p o l y l o g ( N ) = 2 O ( n 2 ) . Мы можем перебить силу таких семян за 2 2 O ( n 2 ) времени и использовать первый, который работает.N=22n2 polylog(N)=2O(n2) 22O(n2)
Чтобы заменить на n f ( n ) , просто вместо этого пусть p n ( x ) = x f ( n ) + f ( n ) .n2 nf(n) pn(x)=xf(n)+f(n)
Интересно, что, если я правильно понимаю, я полагаю, что это означает, что если можно улучшить Тревизан-Сюэ ...
... к псевдодетерминированному алгоритму / алгоритму Белладжио (см. комментарий Эндрю Моргана ниже) можно было бы получить, что ; илиBPEXP⊈P/poly
... чтобы недетерминированной алгоритм , который догадался бит , но затем побежал в р ø л у ( N ) времени, и таким образом, что на любом пути принимающего это делает тот же результат ( ср N P S V ), это будет означать N E X P ⊈ P / p o l y ; илиpolylog(N) poly(N) NPSV NEXP⊈P/poly
... для детерминированного алгоритма можно получить .EXP⊈P/poly
С одной стороны, это говорит о том, почему де-рандомизация леммы о переключении должна быть сложной - аргумент, который я не уверен, был известен раньше! С другой стороны, это кажется мне интересным взглядом на жесткость в сравнении со случайностью (или это на самом деле новое, оракулы в сравнении со случайностью?).
источник