Может ли найти свидетеля быть NP-трудным, даже если мы уже знаем, что он есть?

Типичные примеры NP-сложных задач (клика, 3-SAT, покрытие вершин и т. Д.) Относятся к тому типу, когда мы не знаем, является ли ответ «да» или «нет» заранее.

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

Можем ли мы найти свидетеля в полиномиальное время? Или эта «проблема поиска» может быть NP-трудной?

TFNP - это класс многозначных функций со значениями, которые проверяются полиномиально и гарантированно существуют.

В TFNP существует проблема, которая является FNP-полной тогда и только тогда, когда NP = co-NP, см. Теорему 2.1 в:

Нимрод Мегиддо и Христос Х. Пападимитриу. 1991. Об общих функциях, теоремах существования и вычислительной сложности. Теор. Вычи. Sci. 81, 2 (апрель 1991), 317-324. DOI: 10.1016 / 0304-3975 (91) 90200-L

и ссылки [6] и [11] внутри. PDF доступен здесь .

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

Согласно Ханне, Линиалу и Сафре [1] (см. Третий абзац), уже из классической работы Карпа 1972 года следует, что раскраска 3-раскрашиваемого графа в 3 цвета является NP-трудной. (Их работа расширяет это, чтобы показать, что 4-раскрашивающие 3-раскрашиваемые графы все еще NP-трудны).

Обратите внимание, что это не противоречит ответу Рахула Савани . Это связано с тем, что для всех бинарных отношений в FNP мы должны иметь возможность проверить за полиномиальное время, находится ли в отношении. Учитывая, что решение о том, является ли 3-раскрашиваемый граф с 3 цветами NP-полными, маловероятно, что проблема нахождения 4-раскраски в 3-раскрашенном графе лежит в FNP, поскольку мы не можем проверить достоверность ввода за полиномиальное время. , Таким образом, нет никакого противоречия с результатом Мегиддо-Пападимитриу.P ( x , y ) $P$$P(x,y)$$x$

[1] Ханна, Санджив, Натан Линиал и Шмуэль Сафра. «О твердости аппроксимации хроматического числа». Теория и вычислительные системы, 1993. Материалы 2-го Израильского симпозиума. IEEE, 1993.

Если NP-отношение является NP-трудным в отношении
ко-недетерминированных сокращений Тьюринга за полиномиальное время только для да-ответа , то, Доказательство: если NP-отношение является NP-сложным относительно ко-недетерминированных сокращений Тьюринга за полиномиальное время только для да-ответа , то:$\: NP = coNP \;$

Пусть будет таким трудным отношением, и пусть будут да-ответ только со-недетерминированы полиномиальное время восстановления Тьюринг от до . Пусть - алгоритм coNP, определяемый как: Попытайтесь разобрать предполагаемый анти- сертификат во внутренний сертификат и ответы. Если это не помогло, выведите YES, иначе попытайтесь запустить на внутреннем анти-сертификате, задав тот же ответ, который был дан ранее для повторных запросов и с использованием ответов от (внешний) анти-сертификат для всех других запросов оракула. M ′ S A T $R$$M'$$SAT$$R$$\:$$M$
$\;$
$\;$$M'$
$\;$
$\;$$\:$Если сделает более отчетливым запросов, кроме количества ответов или любого из его запросов, не будет связано с на ответ этого запроса или будет выводить YES, выводит YES, иначе выводит NO. Поскольку наличие оракула для просто накладывает независимые условия на ответы оракула, а - сокращение только для ответа «да», пары запрос-ответ, создаваемые и действительный анти-сертификат всегда могут быть расширены до оракула для , так что решает$M'$
$\;$$R$
$\;$ M M R M ′ M ′ R M S A $M'$$M$$M$
$R$
$M'$$M'$
$R$$M$$SAT\hspace{-0.02 in}$,
Таким образом, Поскольку является трудным относительно детерминированных сокращений за полиномиальное время,, По симметрии, Таким образом, Следовательно, если NP-отношение является NP-сложным относительно ко-недетерминированных сокращений Тьюринга за полиномиальное время только для да-ответа , то, $\: SAT\in coNP \;$
Н $SAT$$NP$$\: NP\subseteq coNP \;$
$\: coNP \subseteq NP \;$$\;\;\;\;$$\: NP = coNP \;$



$\: NP = coNP \;$

Это немного зависит от точной интерпретации вашего вопроса, но я думаю, что ваш сценарий может быть в общих чертах описан как проблема «ВЫЧИСЛИТЬ Y», где дан некоторый универсально фиксированный алгоритм полиномиального времени и полиномиальное на входе , выведите строку , такую, что выдает 1, а всегда существует для всех возможных .$T$$p$$\langle x, 1^n \rangle$$y \in \{0,1\}^{p(n)}$$T(x,y,1^n)$$y$$x$

Тогда возникает один вопрос: подразумевает ли алгоритм полиномиального времени для «COMPUTE Y»$P = NP$

В этом случае предположим, что вы можете решить (скажем) 3SAT за полиномиальное время с постоянным числом обращений к оракулу, который решает «COMPUTE Y», т.е. некоторый алгоритм где если выполнимо, противном случае. Переверните выходной бит, чтобы получить , алгоритм, в котором если выполнимо, и если неудовлетворительно.$A$$A(\phi) = 1$$\phi$$A(\phi)=0$$\bar{A}$$\bar{A}(\phi) = 0$$\phi$$\bar{A}(\phi) = 1$$\phi$

Преобразуйте этот алгоритм (который использует оракул для «COMPUTE Y») в недетерминированный алгоритм (который не использует оракулов), просто заменив каждый вызов оракула недетерминированной догадкой которую вы можете проверить с помощью вызова , Теперь у вас есть недетерминированный алгоритм, который успешно решает неудовлетворительные экземпляры 3CNF, поэтому уТНР=СОН$\bar{A}$$y$$T$$NP = coNP$

Кроме того, если , это означает, что все полные задачи (такие как -clique или 3SAT) имеют небольшие вариации, чье решение проблемы легко (всегда «да»), но чья поисковая версия является труднойN P K N $NP = coNP$$NP$$k$$NP$