Является ли ?

37

Мы знаем, что первый уровень полиномиальной иерархии (т.е. NP и co-NP) находится в PP, и что . Мы также знаем из теоремы Тоды, что . $PP \subseteq PSPACE$ $PH \subseteq P^{PP}$

Знаем ли мы ? Если нет, то почему с оракулом сильнее ? Возможно ли, что и ? $PH \subseteq PP$ $P$ $PP$ $PP$ $PH \nsubseteq PP$ $PP \nsubseteq PH$

Этот вопрос очень прост, но я не нашел никаких ресурсов для его решения.

Я задал этот связанный, но гораздо менее конкретный вопрос о математическом переполнении, прежде чем узнавать больше об этой теме.

Вот несколько связанный (но другой) вопрос: ли $coNP^{\#P}=NP^{\#P}=P^{\#P}$ ?

Обновление: посмотрите на вопрос Ноама Нисана здесь: Больше на PH в PP?

cc.complexity-theory counting-complexity polynomial-hierarchy Гек Беннетт
источник

37

Гек, как указывали Лэнс и Робин, у нас есть оракулы, относительно которых PH нет в PP. Но это не отвечает на ваш вопрос, какова была ситуация в «реальном» (нерелятивизированном) мире!

Короткий ответ: (как и во многих других случаях в теории сложности) мы не знаем.

Но более длинный ответ состоит в том, что есть очень веские основания предполагать, что действительно PH ⊆ PP.

Во-первых, теорема Тоды подразумевает PH ⊆ BP.PP, где BP.PP - это класс сложности, который «относится к PP, а BPP к P» (другими словами, PP, где вы можете использовать рандомизацию, чтобы решить, какое вычисление MAJORITY вы хотите выполнить. выполнения). Во-вторых, при вероятных гипотезах дерандомизации (аналогичных тем, которые, как известно, подразумевают P = BPP, по Нисану-Вигдерсону, Импальяццо-Вигдерсону и т. Д.), Мы имели бы PP = BP.PP.

Приложение, чтобы ответить на ваши другие вопросы:

(1) Я бы сказал, что в любом случае у нас нет убедительной интуиции в вопросе о том, PP = P ^PP . Мы знаем из результатов Beigel-Reingold-Spielman и Fortnow-Reingold, что PP закрыт при неадаптивных (таблица истинности) сокращениях. Другими словами, машина P, которая может делать параллельные запросы к оракулу PP, не более мощна, чем сам PP. Но тот факт, что эти результаты полностью разбиваются на адаптивные (непараллельные) запросы к оракулу PP, говорит о том, что, возможно, последние действительно более мощные.

(2) Аналогично, NP ^PP и coNP ^PP могут быть еще более мощными, чем P ^PP . И PP ^PP может быть еще более мощным, и так далее. Последовательность P, PP, P ^PP , PP ^PP , P ^{PP ^ PP} и т. Д. Называется счетной иерархией , и как люди предполагают, что PH бесконечен, так и можно предположить (хотя, возможно, с меньшей уверенностью!), Что CH бесконечен. Это тесно связано с убеждением, что в пороговых схемах с постоянной глубиной (т. Е. В нейронных сетях) добавление большего количества слоев пороговых элементов дает вам больше вычислительных возможностей.

Скотт Ааронсон
источник

7

Скотт, меня немного смущает утверждение, что «правдоподобно» PP будет содержать PH. Первое отделение PH от PP через оракулы имеет в своем комбинаторном ядре оригинальное разделение Minski & Papert, согласно которому AND-of-ORs не могут быть смоделированы пороговым затвором степени полилога. Я думаю, что неоднородная версия Toda моделирует AC0 распределением вероятности по пороговым значениям степени полилога, что дает правильный ответ whp. Таким образом, на неоднородном уровне «BP» -Gate добавляет значительную мощность, в отличие от неоднородных P против BPP или NP против AM. Так, например, PH в PP со случайным оракулом?

Ноам

Ноам, разве ПП со случайным оракулом не содержит BP.PP? (Я не понимаю, почему это не должно быть.) Если это так, то уверен, что PH в PP со случайным оракулом. Но позвольте мне задать еще один вопрос: есть ли класс сложности C, для которого у нас есть веские основания полагать, что C не равен BP.C?

Скотт Ааронсон

Вам понадобится усиление, чтобы показать, что PP = BP.PP со случайным оракулом - я не понимаю, как это сделать. Даже неравномерно, я не вижу, что PH в PP / поли. Разве не кажется, что AND-of-OR, не находящиеся в пороге степени полилога, указывают на то, что даже неравномерно PH не присутствует в PP?

Ноам

Вот документ, который показывает BP.PP = PP в соответствии с правдоподобной гипотезой: www.cs.uwyo.edu/~jhitchco/papers/hhdcc.ps

Скотт Ааронсон

8

Что я упустил, так это то, что Fortnow и Reingold показали, что PP закрывается при достоверных сокращениях - закрытии, которое необходимо для дерандомизации с использованием PRG (или неравномерно, или со случайным оракулом). Однако я все еще озадачен здесь и сформулировал вопрос об этом: cstheory.stackexchange.com/questions/3331/more-on-ph-in-pp

Noam

23

У Ричарда Бейгеля есть оракул, относительно которого не содержится в PP. $P^{NP}$

Лэнс Фортноу
источник

20

Верещагин [Ver] показал, что существует оракул, относительно которого AM не содержится в PP. (Этот результат кажется несопоставимым с результатом против PP.) $P^{NP}$

[Вер] Н.К. Верещагин. О силе ПП , Слушания IEEE Сложность'92, с. 138-143, 1992.

Робин Котари
источник

13

Кое-что, что не было упомянуто до сих пор (насколько я могу видеть) и что относится к нерелятивизированному миру, заключается в следующем:

P H \subseteq P P if Q M A = P P .

$PH \subseteq PP \quad\mbox{ if }\quad QMA = PP.$

Это было замечено Вялым в этой статье и основано на усилении двух теорем:

Теорема Тоды - Вялый показывает, что для « машины» достаточно имитировать одного запроса к « оракулу » . $\sharp P$ $P$ $PH$
Включение доказано Китаевым и Ватроусом. Вялый доказывает, что также находится в , классе, который содержится в . $QMA \subseteq PP$ $QMA$ $A_0PP$ $PP$

Алессандро Косентино
источник

Является ли ?

Ответы: