Сложность поиска второго решения при правильном решении NP-полной задачи

17

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

Учитывая решение для экземпляра NP-полной задачи, есть ли решение для ? $S$ $I$ $S' \neq S$ $I$

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

Другой вопрос касается именно этой проблемы, связанной с SAT.

Я надеюсь, что я не спрашиваю что-то действительно простое; Похоже, что у Гэри и Джонсона нет подобных примеров.

Спасибо
Марк С.

cc.complexity-theory reference-request np-hardness unique-solution Марк С.
источник

Отметьте, если cstheory.stackexchange.com/questions/1639/… отвечает на ваш вопрос, дайте мне знать, и мы можем пометить его как дубликат. Я спрашиваю, потому что ваш вопрос кажется довольно открытым, и, возможно, ответы там могут помочь

Suresh Venkat

Ах, да, похоже на это отвечает. Ясно, что «Другая проблема решения» - это то, что я искал. Спасибо!

Марк С.

1

Ответ Цуёси кажется совершенно отличным от других, поэтому я не уверен, что имеет смысл закрыть этот вопрос. Может быть, Марк, вы могли бы добавить примечание к вопросу переадресации читателей на другой вопрос (который относится к SAT)?

Суреш Венкат

15

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

Ято и Сета [YS03] (оба являются моими коллегами, когда я был студентом) предлагают общую структуру, чтобы доказать NP-полноту такого рода проблем, где они называются Другая проблема решения или ASP, и доказать NP-полноту ASP много загадок. Они рассматривают ограниченное понятие сокращений между проблемами отношений, называемых сокращениями ASP, и показывают, что NP-твердость ASP сохраняется при сокращениях ASP, и показывают, что многие известные сокращения могут фактически рассматриваться как изменения, вносимые в сокращения ASP, между проблемами естественных отношений.

[YS03] Такаюки Ято и Такахиро Сета. Сложность и полнота поиска другого решения и его применения к головоломкам. Сделки IEICE по основам электроники, связи и компьютерных наук , E86-A (5): 1052–1060, май 2003 г.

Цуёси Ито
источник

1

Я знаю человека, который рассматривает это как возможное направление для кандидатской диссертации, и мы кратко поговорили об этом, хотя я ничего не знаю об этой области. Не похоже, что с тех пор, как вы цитируете статью, было много продолжений, хотя, возможно, мои навыки поиска слабые. Вам известны какие-либо важные документы с 2003 года?

Аарон Стерлинг

3

@ Аарон: Есть и другие проблемы, показанные как полные FNP при сокращении ASP. Также есть несколько статей на эту тему, написанных Такаюки и другими (в том числе одна статья, в которой я соавтор :)), и Такаюки написал диссертацию на эту тему. Одним из более поздних улучшений является формулировка, основанная на проблемах обещания, которая становится особенно важной, когда мы имеем дело с PSPACE-полнотой и EXP-полнотой ASP. К сожалению, ни одна из бумаг не доступна в свободном доступе (я чувствую себя глупо, но даже я не могу получить доступ к своей собственной газете за платным доступом). Вы можете связаться с ним.

Цуёси Ито

2

+1 за отличный ответ и за «даже я не могу получить доступ к своей собственной газете за платной стеной», хе-хе

Даниэль Апон

7

По заданной схеме Гамильтона в графе найдите другую схему Гамильтона. Это FNP-завершено. Интересно, что существуют проблемы, в которых «другое решение» гарантированно существует с помощью аргумента четности. Например: если дана схема Гамильтона в 3-регулярном графе, найдите вторую схему Гамильтона. Отметим, что нахождение гамильтоновой схемы в 3-регулярном графе является NP-полным. Нахождение второго, учитывая, что граф гамильтониан, находится в PPA.

Смотрите мой блог для более подробной информации.

Шива Кинтали
источник

NAE-SAT также. у него всегда есть четное количество решений.

Суреш Венкат

Согласно вышеупомянутой дихотомии, Другой NAE-SAT является полиномиально разрешимым (как указано в статье).

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

Конечно. но NAE-SAT намного проще: возьмите данное задание и переверните его. линейное время! :)

Суреш Венкат

7

Лоран Джубан из теоремы дихотомии для обобщенной задачи об уникальной удовлетворяемости доказал теорему дихотомии для другой SAT, определяемой как:

Вход: пропозициональная формула и удовлетворяющее задание (модель) of $\phi$ $m$ $\phi$

Вопрос: Есть ли другое удовлетворяющее присвоение отличное от ? $\phi$ $m$

Вот выдержка из статьи с теоремой о дихотомии:

Теорема 1 (теорема о дихотомии). Пусть - конечное множество логических отношений. Если удовлетворяет одному из условий (1) - (6) ниже, то ДРУГОЕ SAT (S) и УНИКАЛЬНОЕ SAT (S) разрешимы за полиномиальное время. В противном случае ДРУГОЙ SAT (S) является -завершенным, а УНИКАЛЬНЫЙ SAT (S) - -твердым. $S$ $S$ $NP$ $coNP$

Каждое отношение в является 0-действительным и 1-действительным. $S$

Каждое отношение в является комплементарным. $S$

Каждое отношение в является роговым. $S$

Каждое отношение в анти-рогово. $S$

Каждое отношение в аффинно. $S$

Каждое отношение в является 2SAT. $S$

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

Еще один вариант теоремы Шефера, который является ложным, как указано. Пусть

S = {⊥, x \lor y \lor \neg z, x \lor \neg y \lor \neg z}

$S=\{\bot,x\lor y\lor\neg z,x\lor\neg y\lor\neg z\}$

S

$S$

S

$S$

S

$S$

⊥

$\bot$

S^{'}

$S'$

S^{'} = S ∖ {⊥}

$S'=S\setminus\{\bot\}$ подчиняется условию 1, следовательно, оно имеет как минимум два явно заданных удовлетворяющих назначения.

Эмиль Йержабек поддерживает Монику

S

$S$

1

Вот еще один пример из этой статьи ВЫЧИСЛИТЕЛЬНАЯ СЛОЖНОСТЬ ПРИЗНАНИЯ КРИТИЧЕСКИХ НАБОРОВ :

$NP$

$G$

Вопрос : Есть ли другой край-раздел, отличный от данного?

$NP$

$P$ $P$

Вопрос : Есть ли еще один конец латинского квадрата?

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

Сложность поиска второго решения при правильном решении NP-полной задачи

Ответы: