Означает ли «Второй X является NP-полным» «X является NP-полным»?

«Вторая » проблема - это проблема принятия решения о существовании другого решения, отличного от некоторого данного решения для экземпляра проблемы. $X$

Для некоторых задач с завершением второй версией решения является -complete (решающий вопрос о существовании другого решения для задачи с частичным завершением латинского квадрата), в то время как для других он либо тривиален (Second NAE SAT), либо не может быть -complete (Второй гамильтонов цикл в кубических графах) по широко распространенной гипотезе сложности. Я заинтересован в противоположном направлении. $NP$ $NP$ $NP$

Мы предполагаем , естественную проблемы , где существует естественный эффективный верификатор , который проверяет естественное интересное соотношение , где представляет собой экземпляр входного и коротким свидетельством членства в . Все свидетели неразличимы для проверяющего. Достоверность свидетелей должна быть определена путем запуска естественного верификатора, и он не знает ни одного правильного свидетеля (оба примера в комментариях являются решениями по определению). $NP$ $X$ $(x, c)$ $x$ $c$ $x$ $X$

Означает ли «Второй является NP-полным» « является NP-полным» для всех «естественных» проблем ? $X$ $X$ $X$

Другими словами, существует ли какая-либо «естественная» проблема где эта импликация терпит неудачу? $X$ , Или, что то же самое,

Есть ли какая-либо "естественная" проблема в и она не является полной, но ее вторая проблема является полной? $X$ $NP$ $NP$ $X$ $NP$

РЕДАКТИРОВАТЬ : Благодаря комментариям Марцио, меня не интересуют надуманные контрпримеры. Меня интересуют только естественные и интересные контрпримеры для NP-полных задач аналогичные приведенным выше. Приемлемый ответ является либо доказательством выше импликации или контр-примера «Вторая проблема Х» , которая определена для природных, интересных и хорошо известной задачи . $X$ $NP$ $X$

EDIT 2 : Благодаря плодотворной дискуссии с Дэвидом Richerby, я редактировал вопрос внимания , что мой интерес только в естественных проблемах . $X$

РЕДАКТИРОВАТЬ 3 : Мотивация: Во-первых, наличие такого подтекста может упростить доказательства полноты многих проблем . Во-вторых, наличие импликации связывает сложность решения единственности решения проблемы решения существования решения задач . $NP$ $NP$ $NP$

cc.complexity-theory unique-solution Мухаммед Аль-Туркистани
источник

Комментарии не для расширенного обсуждения; этот разговор был перенесен в чат .

Бьёрн Кьос-Ханссен

Ваши EDIT 3 и EDIT 1 не совпадают. Если вы хотите, чтобы это был общий результат, полезный для упрощения доказательств полноты NP, вы также не можете сказать, что вам нужны только «не надуманные» контрпримеры. Также было бы полезно иметь определение «естественно / интересно», которое не основано на личном мнении.

Крис Джефферсон

Ответы:

Нет,

Рассмотрим задачу «Найти подмножество набора целых чисел S, сумма которого равна 0».

Эта проблема тривиальна, так как можно вернуть пустое множество.

Однако нахождение второго решения после возврата пустого множества является хорошо известной проблемой суммы подмножеств, которая, как известно, является NP-полной.

Крис Джефферсон
источник

Если вы не можете определить «неестественную» проблему, это не имеет значения. Люди определяют сотни вариантов проблем, таких как сумма подмножеств и SAT.

Крис Джефферсон

@ Мохаммед: вот еще один контрпример; Я оставляю на ваше усмотрение решение, является ли оно естественным или нет: в игре с биматрицами всегда есть хотя бы одно равновесие Нэша, и сложно решить, является ли игра с биматрицами более чем одним равновесием Нэша [Gilboa and Zemel, GEB 1989] , Конструкция принимает формулу SAT f и производит игру с определенным равновесием Нэша известной формы, которое всегда существует, так что игра имеет второе равновесие, если формула f выполнима.

Рахул Савани

Вот еще один контрпример, одномерный вариант леммы Спернера, который по духу похож на тот, который предлагает Рахул. Для данной булевой схемы, вычисляющей функцию

(вход предоставляется в двоичном виде) с обещанием, что

, найти число

f : {0, 1, 2, \dots, 2^{n} - 1} \to {0, 1}

$f : \{0,1,2,\ldots,2^n-1\} \to \{0,1\}$

f (0) = 0

$f(0) = 0$

f (2^{n} - 1) = 1

$f(2^n-1)=1$

k

$k$ такой, что

. Такое число всегда существует и его легко найти с помощью бинарного поиска, но трудно решить, существует ли более одной такой позиции, где это происходит.

f (k) = 0

$f(k) = 0$

f (k + 1) = 1

$f(k+1) = 1$

Роберт Эндрюс

NP Complete не означает, что все случаи сложны, только некоторые из них. Существует много тривиальных примеров суммы подмножеств (все задачи, которые содержат 1 и -1, например) и много простых задач SAT (например, 2 SAT), но в целом SAT все еще NP-завершен.

Крис Джефферсон

Ответ должен быть подмножеством набора целых чисел S. {} является подмножеством S, так как пустой набор является подмножеством всех множеств. {ϕ} не является подмножеством S, так как S не содержит ϕ

Крис Джефферсон

Ответ - да (если вместо уменьшения Карпа используется уменьшение ASP). Для уменьшения ASP требуется вычисляемая биекция за полиномиальное время между наборами решений двух задач. Это обеспечивает экономное сокращение между ASP-полными проблемами. Ято и Сета утверждают, что -полнота подразумевает -полноту (Страница 2, второй абзац). Другая проблема решения (ASP) - это именно то, что я называю Второй Х проблемой. $ASP$ $NP$

Одед Голдрайх утверждает, что «все известные сокращения естественных проблем, связанных с , либо экономны, либо могут быть легко модифицированы». ( Вычислительная сложность: концептуальная точка зрения Одед Голдрейх ). Следовательно, вполне вероятно, что сокращения Карпа между естественными NP-полными задачами могут быть изменены, чтобы быть сокращениями ASP. $NP$

Мухаммед Аль-Туркистани
источник

Ваша проблема заключалась в том, подразумевает ли NP-полнота второго решения NP-полноту. То, что они показывают, слабее, они требуют ASP-полноты, так как NP-полноты недостаточно, как указано в комментариях к вашему вопросу.

domotorp

Если кто-то читает это, этот ответ неверен. Легко создать проблему, когда Second X является NP-полной, но X не NP-полной. Например (как обсуждалось в комментариях выше), проблема поиска подмножества набора целых чисел, сумма которого равна 0, является второй X NP-полной, потому что она NP-полная, когда мы отвергаем простое первое решение пустого множества ,

Крис Джефферсон

Π

$\Pi$

Π_{[2]}

$\Pi_{[2]}$

Π

$\Pi$

Π

$\Pi$

Π_{[2]}

$\Pi_{[2]}$

Π_{[2]}

$\Pi_{[2]}$

Π

$\Pi$

Сашо Николов

Для кого-то немного странно задавать вопрос, отвечать на него и затем принимать его, пока идет обсуждение.

Чандра Чекури

@ MohammadAl-Turkistany В моем комментарии говорилось, что ваш ответ, похоже, изменил логику и не отвечает на ваш собственный вопрос. Я ничего не сказал о примере Криса (что для меня выглядит нормально, но я не хочу вдаваться в этот аргумент в комментариях).

Сашо Николов