Проверка уникальных решений SAT

25

Рассмотрим следующую проблему: учитывая формулу CNF и присвоение, которое удовлетворяет этой формуле, есть ли другое удовлетворяющее назначение для этой формулы?

В чем сложность этой проблемы? (Это наверняка есть в NP, но это также NP-hard?)

Что если вам не дано назначение, и вы просто хотите решить, имеет ли формула уникальное удовлетворяющее назначение?

Спасибо.

j--
источник
13
Ваша первая проблема - это часто домашнее задание. Подсказка: если дана любая формула F, создайте формулу F ', где присваивание всех нулей тривиально ее удовлетворяет, и существует второе удовлетворяющее присваивание F', если F выполнимо.
Райан Уильямс
1
@ Сянь-Чи Чанг, у нас было имя Одеда на первой полосе перед твоей повторной пометкой, повторная пометка не срочна, было бы хорошо, если бы его имя оставалось там немного дольше. :)
Kaveh
1
@Kaveh: Ой, прости. Я предполагаю, что я каким-то образом предполагаю, что он останется и будет постоянно давать все больше и больше хороших ответов, поэтому его имя будет часто появляться на главной странице :)
Сянь-Чи Чанг 張顯 之
@ Сянь-Чи Чанг, я тоже на это надеюсь. :)
Kaveh

Ответы:

27

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

Проблема определения того, имеет ли данная формула CNF уникальное удовлетворяющее назначение или нет (поэтому вы должны ответить «нет», если формула не имеет удовлетворяющих назначений или более одного удовлетворяющего назначения), является полной в США . США содержит как UP, так и CONP .

Ссылки

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

Изменить : более ранняя версия (редакция 1) этого ответа содержала путаницу между версией решения и версией поиска. Это было исправлено.

Цуёси Ито
источник
6
Просто примечание: NP-полнота «еще одной проблемы решения» - это фольклор, известный задолго до 2003 года. (Может быть, есть ссылка 1970-х годов, но доказательства настолько просты, что я сомневаюсь в этом.)
Райан Уильямс,
@ Райан: Спасибо за примечание. Я отредактировал ответ, чтобы сделать связь с [YS03] более понятной.
Цуёси Ито
22

Я вспоминаю, как Йорам Мозес и я изучали эту проблему в середине 1980-х годов (в свете какого-то приложения) и обнаружили, что для многих естественных проблем с NPC проблема поиска второго / альтернативного решения (или решения, существует ли таковая) - это NPC. Затем мы узнали, что это было известно, но я не помню ссылки, и не смогли найти один (то есть, тот, что был до середины 1980-х годов) сейчас. Но я уверен, что правильно помню все вышеизложенное.

Просто комментарий к Райану. Тот факт, что теорема может быть дана в качестве упражнения в современных классах, не делает ее менее привлекательной. Он должен был быть опубликован в газете с соответствующим названием в то время, когда он был обнаружен ...

Одед Голдрайх

Одед Голдрайх
источник
15
Эй, добро пожаловать на борт! Я так рад видеть вас здесь :)
MS Dousti
12

Здесь я пишу отрывок из следующей статьи:

Valiant, LG и Vazirani, VV 1986. NP так же просто, как обнаруживать уникальные решения. Теор. Вычи. Sci. 47, 1 (ноябрь 1986), 85-93. DOI = http://dx.doi.org/10.1016/0304-3975(86)90135-0

Для каждой известной NP-полной задачи число решений ее экземпляров варьируется в широких пределах, от нуля до экспоненциального числа. Поэтому естественно спросить, вызвана ли эта неразрешимость NP-полной проблемы этой широкой вариацией. Мы даем отрицательный ответ на этот вопрос, используя понятие рандомизированной полиномиальной сводимости по времени. Мы показываем, что проблемы различения экземпляров SAT, имеющих нулевое или одно решение, или поиска решений для экземпляров SAT, имеющих уникальное решение, столь же сложны, как и SAT, при рандомизированных сокращениях.

Я также предлагаю посмотреть на соответствующий документ:

Beigel, R., Buhrman, H., и Fortnow, L. 1998. NP может быть не так просто, как обнаружить уникальные решения. В материалах тридцатого ежегодного симпозиума ACM по теории вычислений (Даллас, Техас, США, 24–26 мая 1998 г.). STOC '98. ACM, Нью-Йорк, Нью-Йорк, 203-208. DOI = http://doi.acm.org/10.1145/276698.276737

М.С. Дусти
источник
6

Dпзнак равно{(L1L2)|L1Nп,L2СоNп}

Андреас Бласс и Юрий Гуревич, Об уникальной проблеме выполнимости,

Мухаммед Аль-Туркистани
источник
1
Небольшой момент: вторая проблема не является проблемой обещания.
Цуёси Ито
1
Я понял это и исправил, но все равно спасибо за то, что заметил это!
Цуёси Ито
6
Кстати, я ничего не скопировал из вашего ответа, поэтому я понятия не имею, к чему относится ваш следующий комментарий: «Когда вы копируете из другого ответа, укажите это». Я скопировал ссылку на мой ответ из другого моего поста. на MathOverflow ( mathoverflow.net/questions/31251/… ), но я не думаю, что вы имеете в виду это.
Цуёси Ито
2

Решение обеих проблем, UNIQUE SAT, а также ANOTHER SAT, с полной классификацией сложности, можно найти в статье.

Л. Джубан: теорема о дихотомии для обобщенной задачи единственной выполнимости http://link.springer.com/chapter/10.1007%2F3-540-48321-7_27

Мики Герман
источник