Последствия NP = PSPACE

30

Каковы будут неприятные последствия NP = PSPACE? Я удивлен, что ничего не нашел по этому поводу, учитывая, что эти классы являются одними из самых известных.

В частности, будет ли это иметь последствия для низших классов?

Денис
источник
4
Непосредственное следствие, или, скорее, переформулировка личности: верификатору не нужно будет сообщать проверяющему, никогда!
Алессандро Косентино

Ответы:

28

Если , это будет означать:NP=PSPACE

  • P#P=NP
    То есть, подсчет решений проблемы в будет многократно сводиться к нахождению единственного решения;NP

  • PP=NP
    То есть рандомизированные алгоритмы за полиномиальное время с вероятностью успеха, произвольно близкой к 1/2, сводятся за полиномиальное время к рандомизированным алгоритмам за полиномиальное время с односторонней ошибкой, где принимаются экземпляры YES с сколь угодно малой вероятностью;

  • MA=NP
    То есть для любой задачи, которая проверяется за полиномиальное время, рандомизация в лучшем случае обеспечивает ускорение за полиномиальное время (но это всего лишь следствие коллапса иерархии за полиномиальное время);

  • BQPNP
    То есть любая проблема, которая решается квантовым компьютером, имеет легко проверяемые сертификаты для ее ответов; это было бы важным положительным результатом в философии квантовой механики и, вероятно, было бы полезно для усилий по созданию квантовых компьютеров (для проверки того, что они делают то, что они должны делать).

Все это из-за содержания классов в левой части в (хотя у нас также есть ).B Q P P PPSPACEBQPPP

Ниль де Бодрап
источник
1
Можете ли вы указать на ссылку, где означает, что . СпасибоB Q PN PNP=PSPACEBQPNP
Tayfun Pay
2
@TayfunPay Вы в основном хотите ссылку на . Ссылка для этого - BV97 . Однако вы также можете доказать, что . Смотрите следующую лекцию для интуиции: scottaaronson.com/democritus/lec10.htmlB Q PP PBQPPSPACEBQPPP
Алессандро
2
@AlessandroCosentino Да, я знал, что и что . Я думаю, мне просто нужно было указать, чтобы покачивать в памяти! Благодарность! :)N PP PP S P A C EBPPBQPPPPSPACENPPPPSPACE
Tayfun Pay
23

Один момент, который неявно, но явно не упоминается, это то, что мы получили бы . Хотя это эквивалентно свертыванию в , это непосредственно следует из того факта, что замкнут относительно дополнения, что тривиально доказать.П Н Н П П С П А С ЕNP=coNPPHNPPSPACE

Я думаю, что стоит по себе из-за большого числа удивительных последствий, которые он имеет: существуют короткие доказательства, свидетельствующие о том, что граф не является 3-раскрашенным, * не * гамильтонианом , когда два графа * не * изоморфны, ... и (в некотором смысле в более общем смысле) существует некоторая система доказательств Кука-Рекхоу, в которой каждая пропозициональная тавтология имеет доказательство полиномиального размера.NP=coNP

Джошуа Грохов
источник
12

Если NP=PSPACE

1) полиномиальная иерархия разрушится до .NP

2) Теперь у нас будет поскольку мы знаем, что P S P A C EN LNPNLPSPACENL

---ОБНОВИТЬ---

3) Известно, что , где они представляют собой ограниченные логарифмическим пространством версии N P , C = P и P P соответственно. Тогда , по определению , ни один из этих классов сложности может быть равна Н Р в предположении , что Н Р = Р С Р С Е .NLC=LPLNPC=PPPNPNP=PSPACE

Тайфун Пей
источник
1
Это тривиальные последствия после PH PSPACE и NL PSPACE, я надеялся на более удивительные последствия, например что-то между NL и P или любое новое отношение между двумя классами «строго» ниже NP.
Денис
1
Обратите внимание, что если вы рассматриваете NL как класс языков, у которых есть решения, которые можно проверить в пространстве журналов, даже если каждый символ решения читается не более одного раза (хотя логарифмически многие из них могут храниться на рабочей ленте в любой момент времени) тот факт, что он отличается от NP, указывает на то, что существует класс L ', который является родственником L , включающий в себя машины Тьюринга с двумя входными лентами, но один из которых предназначен для однократного чтения, а другой - нет, и который отличается от P ( где из-за того, что на рабочей ленте имеется полиномиальное пространство, ограничения на однократное чтение не имеют значения).
Ниль де Бёдрап,
1
@dkuper Вы также будет иметь , где P L является логарифмическая пространство ограничено версией P P , а также # LN P , где # L логарифмическая пространство ограничено версия # P . PLNPPLPP#LNP#L#P
Tayfun Pay
1
@TayfunPay: (1) почему бы вам не отредактировать свой ответ, чтобы включить отношения из вашего комментария? (2) Как они держатся?
Ниль де Бёдрап,
10

В дополнение к результатам, указанным во всех других ответах, есть один, включающий интерактивные системы проверки ( ), которые являются обобщением N P, где Verifier и Prover обмениваются сообщениями для распознавания языка.IPNP

Известно, что , поэтому, если N P = P S P A C E , это означает, что достаточно только одного сообщения! Для меня более впечатляющим является тот результат, что Verifier не нужно будет бросать вызов Prover и он может доверять самому первому сообщению, посланному ею.IP=PSPACENP=PSPACE

Алекс Грило
источник
Это все еще может зависеть от реализации, хотя? Это означает, что интерактивные проверяющие по-прежнему нуждаются в большем обмене, только существуют другие, имеющие только одно сообщение на одном языке.
Денис
Ну, это будет означать, что одного сообщения достаточно. Если я правильно понял ваш вопрос, то же самое относится и к задачам в P: хотя для них есть алгоритмы с полиномиальным временем, все же можно создать алгоритм экспоненциального времени.
Алекс Грило
2
@AlexGrilo: отсюда мой комментарий под вопросом :)
Алессандро Косентино
@AlessandroCosentino Извините, я этого раньше не видел
Алекс Грило,