Что такое оракул минимальной сложности, который отделяет PSPACE от полиномиальной иерархии?

17

Фон

Известно , что существует оракул такое , что .P S P A C E AP H AAPSPACEAPHA

Даже известно, что разделение справедливо относительно случайного оракула. Неофициально можно интерпретировать это как означающее, что существует много оракулов, для которых и разделены.P HPSPACEPH

Вопрос

Насколько сложны эти оракулы, которые отделяют от . В частности, существует ли оракул такой, что ?P H A D T I M E ( 2 2 n ) P S P A C E AP H APSPACEPHADTIME(22n)PSPACEAPHA

Есть ли у нас оракул такой, что и имеет верхнюю границу известной сложности?P S P A C E AP H A AAPSPACEAPHAA

Примечание: существование такого оракула может иметь разветвления в теории структурной сложности. См. Следующее обновление ниже для получения дополнительной информации.

Обновление с подробной информацией о технике нижней границы

Утверждение: Если , то для всех оракулов , .A P / p o l y P S P A C E A = P H APSPACE=PHAP/polyPSPACEA=PHA

Эскиз доказательства: предположим, что .PSPACE=PH

Пусть дан оракул . Мы можем построить полиномиальное время оракула Тьюринг машина , что для заданной длины , угадывает схему размера с использованием экзистенциальной количественной оценки и проверяет , что схема принимает решение пути сравнения оценки схемы и результата запроса для каждой длины строки используется универсальное количественное определение.Σ 2 M n p ( n ) A nAP/polyΣ2Mnp(n)An

Далее рассмотрим решение проблемы, которую я называю квантифицированной логической схемой (QBC), где вам дана квантифицированная логическая схема и вы хотите знать, действительна ли она (аналогично QBF). Эта проблема является PSPACE-полной, потому что QBF является PSPACE-полной.

По предположению следует, что QBC . Допустим, для некоторого достаточно большого размера. Пусть обозначает полиномиальное время машина Тьюринга, которая решает QBC.Q B C Σ k k N Σ kPHQBCΣkkNΣk

Мы можем смешиваться вычисление и (подобно тому , как это делается при доказательстве теоремы Карп-Lipton) , чтобы получить полиномиальное время оракул машина Тьюринга , которая решает .N Σ k Q B C AMNΣkQBCA

Неофициально, эта новая машина принимает в качестве входных данных оракула QBC (то есть QBC с воротами оракула). Затем он вычисляет схему, которая вычисляет на входах длины (одновременно удаляя первые два квантификатора). Далее, он заменяет оракула ворота в оракула QBC со схемой для . Наконец, он продолжает применять оставшуюся часть алгоритма полиномиального времени для решения на этом модифицированном экземпляре.n A Σ k Q B CAnAΣkQBC

Теперь мы можем показать условную нижнюю границу.

Следствие: если существует оракул такой, что , то .P S P A C E AP H A N E X P P / p o l yANEXPPSPACEAPHANEXPP/poly

Доказательство Sketch: Предположим , что существует такое , что . Если , мы получим противоречие.P S P A C E AP H A N E X P P / p o l yANEXPPSPACEAPHANEXPP/poly

В частности, если , то согласно приведенному выше утверждению имеем . Однако известно, что подразумевает, что .Р С Р С Е Р Н Н Е Х Р Р / р о л у P S P A C E = P HNEXPP/polyPSPACEPHNEXPP/polyPSPACE=PH

(см. здесь некоторые подробности об известных результатах для P / poly)

Майкл Вехар
источник
3
Вероятно, стоит упомянуть, что предположили, что PSPACE PH. то есть тривиальный оракул, но мы не можем доказать это.
Томас поддерживает Монику
1
Как именно вы определяете релятивизированный PSPACE? Больше чем одна возможность появляется в литературе. В частности, предполагаются ли оракульные запросы полиномиально ограниченными?
Эмиль Йержабек поддерживает Монику
1
Включаете ли вы «построение формул Q», большие монотонные булевы формулы, которые определяют все 2 ^ n qbfs исходной формулы, в PH? См. Введение в QSpace, 2002 Конференция по удовлетворенности, Международный семинар по QBFS, для получения дополнительной информации о формулах Q.
Даниэль Пехоушек
1
Я полагаю, что в качестве нижней границы могу показать, что такое существо в SEH " будет иметь разветвления в теории структурной сложности". Должен ли я опубликовать это довольно скоро (что может означать завтра или может означать через 30 минут), или оставить это без ответа дольше, чтобы вы с большей вероятностью получили ответ с достаточным классом? A
1
Учитывая, что случайные оракулы имеют высокую колмогоровскую сложность, я ожидал бы, что любая вычисляемая верхняя граница для таких оракулов будет иметь заметные последствия. Сильные верхние оценки, такие как однократная экспонента, должны иметь сильные последствия. (Конечно, этот аргумент является чисто эвристическим, и я в настоящее время не знаю, как сделать его строгим.)
Саламон,

Ответы:

9

Я полагаю, что если вы проследите аргумент, приведенный, например, в разделе 4.1 опроса Ker-I Ko , вы получите верхнюю границу . Фактически, мы можем заменить здесь любой функцией где как . Это не совсем то, о чем просили, но это близко.n 2 n f ( n ) f ( n ) n DTIME(22O(n2))n2nf(n)f(n)n

В частности, используя перевод между разделением оракула и нижними границами контура и следуя обозначениям Ко, мы имеем следующее:

  • Диагонализируем по строкам длины где - это « полином» (в некоторых перечислениях алгоритмов поли-времени) и будет указано ниже.p n ( x ) = x n + n n m ( n )t(n)=pn(m(n))pn(x)=xn+nnm(n)

  • Переводя в нижние границы цепей, это означает, что мы рассматриваем схемы ограниченной глубины на входах.2t(n)

  • Требование (см. Стр. 15 Ко) нам нужно чтобы удовлетворить 1m(n)для всехn. Здесьd- глубина схем, против которых мы хотим диагонализировать, или, что эквивалентно, уровеньΣ p d вPH,против которого мы хотим диагонализировать. Чтобы диагонализировать всеPH, просто выберитеdкак функцию отn,то естьω(1); мы можем выбрать такойд1102m/(d1)>dpn(m(n))ndΣdpPHPHdnω(1)dхотя он растет произвольно медленно (возможно, при условии некоторого предположения о вычислимости , но это не должно быть препятствием). Если мы предположим, что d ( n ) является постоянной величиной (хотя это не так, но она будет расти произвольно медленно), то мы увидим, что m ( n ) около 2 n должно работать.d(n)d(n)m(n)2n

  • Это означает , что , поэтому мы ищем нижнюю границу от цепей с ~ 2 2 п 2 входами.t(n)2n222n2

  • Тревисано и Сей (КТС '13) показали , что можно найти задание , на котором данный ограниченную глубину контур на входах не вычисляет соотношение с семени р ø л у л о г ( Н ) длиной.Npolylog(N)

  • Для нас , поэтому p o l y l o g ( N ) = 2 O ( n 2 ) . Мы можем перебить силу таких семян за 2 2 O ( n 2 ) времени и использовать первый, который работает.N=22n2polylog(N)=2O(n2)22O(n2)

Чтобы заменить на n f ( n ) , просто вместо этого пусть p n ( x ) = x f ( n ) + f ( n ) .n2nf(n)pn(x)=xf(n)+f(n)

Интересно, что, если я правильно понимаю, я полагаю, что это означает, что если можно улучшить Тревизан-Сюэ ...

  • ... к псевдодетерминированному алгоритму / алгоритму Белладжио (см. комментарий Эндрю Моргана ниже) можно было бы получить, что ; илиBPEXPP/poly

  • ... чтобы недетерминированной алгоритм , который догадался бит , но затем побежал в р ø л у ( N ) времени, и таким образом, что на любом пути принимающего это делает тот же результат ( ср N P S V ), это будет означать N E X PP / p o l y ; илиpolylog(N)poly(N)NPSVNEXPP/poly

  • ... для детерминированного алгоритма можно получить .EXPP/poly

С одной стороны, это говорит о том, почему де-рандомизация леммы о переключении должна быть сложной - аргумент, который я не уверен, был известен раньше! С другой стороны, это кажется мне интересным взглядом на жесткость в сравнении со случайностью (или это на самом деле новое, оракулы в сравнении со случайностью?).

Джошуа Грохов
источник
3
Одна из проблем, которая здесь скрыта, заключается в том, что созданный оракул должен быть одним фиксированным оракулом, чтобы его можно было решить в BPEXP или где-либо еще. Если вы просто выберете случайное семя хорошего генератора, тогда, хотя у вас действительно будет какой-то оракул, который вы работаете, вы не обязательно получите процедуру принятия решения для этого оракула, поскольку разные семена дают (в общем) разные оракулы. Вам нужно было сделать что-то большее, например, найти каноническое семя, чтобы сделать конструкцию действительно «конструктивной».
Эндрю Морган
3
Даже если аргумент не дает BPEXP, можете ли вы снизить сложность до конечного уровня EXPH?
Эмиль Йержабек поддерживает Монику
2
@ EmilJeřábek: Без проверки деталей, я думаю, должно работать. Угадайте семя, используя , убедитесь, что оно работает, используя , а затем убедитесь, что это лексикографически наименьшее семя, используя ¬ = ¬ , в общей сложности . Σ3EXP¬=¬
Джошуа
2
@EmilJerabek: Конечно, если бы мы могли, по крайней мере, довести это до это было бы еще лучше (немыслимо без подтверждения нижних границ новой схемы), но я пока не вижу, как это сделать ...MAEXP
Джошуа
2
@JoshuaGrochow Да, твой оригинальный пост кажется нормальным. Я возражал против вашего ответа Эмилю, который предположил, что оракул может быть сделан в EXPH, где время работы является одноэкспоненциальным. Оглядываясь назад, я должен был быть более ясным об этом.
Эндрю Морган