Последствия полных задач для NP пересекает coNP

24

Каковы последствия наличия полных проблем в ?NPcoNP

Маркос Вильягра
источник
См. Также mathoverflow.net/questions/34889/…
Юкка Суомела
Я знаю эту ссылку. Мой вопрос о последствиях. Например, если язык L завершен для то PH падает до уровня или что-то в этом роде. iNPcoNPi
Маркос Вильягра
На самом деле, я задал тот же вопрос, что и комментарий в этой ссылке, но я хотел, чтобы это был настоящий вопрос.
Маркос Вильягра
2
Да, я знаю, что вы знаете, но страница mathoverflow предоставляет полезную справочную информацию для других.
Юкка Суомела

Ответы:

18

Это (широко) открытая проблема; как в, мы почти ничего не знаем. В частности, из-за хитрости в доказательстве неполадок нам нужны совершенно другие методы доказательства, чем в настоящее время. Таким образом, обсуждение последствий должно разумно включать касательную тему: «Что бы значило иметь такие мощные, новые методы доказательства?»NPcoNP

Для сравнительно недавнего обсуждения этой темы есть 26-й столбец NP-Полнота Дэвида Джонсона в ACM Transactions on Algorithms от 2007 ( PDF ). Позвольте мне перефразировать кое-что из того, что говорит Дэвид относительно вопроса о доказательстве существования проблем, и добавить мои мысли:NPcoNP

В настоящее время у нас есть только «слабые» естественные кандидаты на членство в в том смысле, что самым убедительным доказательством их членства является то, что нам пока не удалось найти для них алгоритм полиномиального времени. Он перечисляет пару кандидатов: МАЛЕНЬКИЙ ФАКТОР, ПРОСТАЯ СТОХАСТИЧЕСКАЯ ИГРА и ИГРА СРЕДНЕГО ВЫПЛАТА. Некоторые из дополнительных «странностей» этих проблем проистекают из лучших эвристических времен выполнения для их решения, например, МАЛЫЙ ФАКТОР, также известный как INTEGER FACTOR , имеет случайную временную сложность . (Если в существуют полные проблемы , то такая субэкспоненциальная (ни чисто экспоненциальная, ни полиномиальная)NPcoNPPk p o l y ( n ) 2 kpoly(n)2klog(k)NPcoNPPвремя выполнения эндемик класса? )

В частности, мы бы хотели доказать что-то вроде: проблема A существует только в тогда и только тогда, когда , то есть результат полноты, подобный теореме Кука для 3SAT и . Для такие доказательства повсеместно включают сокращения за полиномиальное время (и исправьте ваши любимые дополнительные ограничения, например, сокращения Кука, сокращения Карпа). В результате, при использовании методов сокращения за полиномиальное время должен существовать случай, когда существует распознаваемое представление класса за полиномиальное время. Для мы можем использовать недетерминированные машины Тьюринга, которые останавливаются в полиноме,PNPcoNP=PNPNPNPp(|x|)P S P A C E Pколичество шагов Как Давид указывает, у нас есть подобные представления для других классов (где статус понятнее) , таких как и # .PSPACEP

Сложность, однако, с предоставлением аналогичного представления для NPcoNP состоит в том, что «естественный» аналог позволяет нам встроить проблему остановки в представление и поэтому неразрешим . То есть рассмотрим следующую попытку представить NPcoNP с помощью двух недетерминированных машин Тьюринга, которые, как утверждается, распознают дополнительные языки:

Вопрос: останавливается ли машина Тьюринга M на входе x0,1n ?

Построить две линейные машины Тьюринга M1 и M2 следующим образом. На входе y , M1 считывает вход и всегда принимает. M2 всегда отвергает, если |y||x|и M принимает x на шагах |y|,

Следовательно, M1 и M2 принимают дополнительные языки, если только M не останавливается на входе x . Следовательно, противоречие, решение о том, принимают ли две машины Тьюринга за полиномиальное время дополняющие языки, неразрешимо.

Таким образом, «естественное» представление задач NPcoNP не распознается за полиномиальное время. Остается вопрос: как вы представляете проблемы NPcoNP , чтобы они распознавались за полиномиальное время?

Там не было никакой существенной работы по этому вопросу, но ее успешное решение необходимо доказать полноту в NPcoNP . Следовательно, я утверждаю, что существование метода доказательства, который может разрешить полноту NPcoNP будет большей историей здесь, а не «автоматическим» результатом NPcoNP -полных задач ( например, классы сложности, возможно, разрушающиеся), о которых мы уже знаем (или, скорее, будем знать , гипотетически в будущем).

Даниэль Апон
источник
1
спасибо за PDF. Еще не читал, но буду. Есть эта статья: «Об общих функциях, теоремах существования и вычислительной сложности». Нимрод Мегиддо и Христос Пападимитриу. Теоретическая информатика 81, 1991. Речь идет не о , а о связанном с ним классе функций TFNP, то есть T F N P = F ( N P c o N P ) . Существует следующая теорема: «Существует полная FNP-проблема в TFNP, если NP = coNP». Учитывая, что задачи поиска и решения полиномиально связаны, распространяется ли эта теорема также на N PNPcoNPTFNпзнак равноF(NпсоNп) ? Если это так, это будет означать большой крах в PH. Это верно? NпсоNп
Маркос Вильягра
Это не переводит напрямую (как я полагаю, вы подразумеваете). Обратите внимание, что теорема относится не только к ЛЮБОЙ полной задаче, но и к полной FNP-задаче. Это равносильно высказыванию «Существует NP-полная проблема в NP \ cap coNP, если NP = coNP». Насколько мне известно, вполне возможно, что у NP \ cap coNP есть полные проблемы, отличные от NP-полных проблем, без разрушения PH . (Ссылка для развлечения.;))
Даниэль Апон
Примечание: все еще считается маловероятным, что ситуация, которую я описал выше как возможную, имеет место по тем же причинам в ответе.
Даниэль Апон