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

17

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

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

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

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

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

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

Марк С.
источник
Отметьте, если 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, определяемой как:

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

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

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

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

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

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

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

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

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

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

Мухаммед Аль-Туркистани
источник
Еще один вариант теоремы Шефера, который является ложным, как указано. Пусть Sзнак равно{,ИксY¬Z,Икс¬Y¬Z}SSSS'S'знак равноS{}подчиняется условию 1, следовательно, оно имеет как минимум два явно заданных удовлетворяющих назначения.
Эмиль Йержабек поддерживает Монику
S