Рассмотрим следующую проблему: учитывая формулу CNF и присвоение, которое удовлетворяет этой формуле, есть ли другое удовлетворяющее назначение для этой формулы?
В чем сложность этой проблемы? (Это наверняка есть в NP, но это также NP-hard?)
Что если вам не дано назначение, и вы просто хотите решить, имеет ли формула уникальное удовлетворяющее назначение?
Спасибо.
Ответы:
Проблема определения того, имеет ли данная формула CNF удовлетворяющее назначение, отличное от заданного, легко показывается, что NP-полная, путем преобразования формулы CNF для добавления одного тривиального решения. Эта проблема называется «Другой проблемой решения (ASP) SAT» в [YS03], где она используется для систематического доказательства того, что (версии решения) ASP многих других проблем также являются NP-полными.
Проблема определения того, имеет ли данная формула CNF уникальное удовлетворяющее назначение или нет (поэтому вы должны ответить «нет», если формула не имеет удовлетворяющих назначений или более одного удовлетворяющего назначения), является полной в США . США содержит как UP, так и CONP .
Ссылки
[YS03] Такаюки Ято и Такахиро Сета. Сложность и полнота поиска другого решения и его применения к головоломкам. Сделки IEICE по основам электроники, связи и компьютерных наук, E86-A (5): 1052–1060, май 2003 г.
Изменить : более ранняя версия (редакция 1) этого ответа содержала путаницу между версией решения и версией поиска. Это было исправлено.
источник
Я вспоминаю, как Йорам Мозес и я изучали эту проблему в середине 1980-х годов (в свете какого-то приложения) и обнаружили, что для многих естественных проблем с NPC проблема поиска второго / альтернативного решения (или решения, существует ли таковая) - это NPC. Затем мы узнали, что это было известно, но я не помню ссылки, и не смогли найти один (то есть, тот, что был до середины 1980-х годов) сейчас. Но я уверен, что правильно помню все вышеизложенное.
Просто комментарий к Райану. Тот факт, что теорема может быть дана в качестве упражнения в современных классах, не делает ее менее привлекательной. Он должен был быть опубликован в газете с соответствующим названием в то время, когда он был обнаружен ...
Одед Голдрайх
источник
Здесь я пишу отрывок из следующей статьи:
Valiant, LG и Vazirani, VV 1986. NP так же просто, как обнаруживать уникальные решения. Теор. Вычи. Sci. 47, 1 (ноябрь 1986), 85-93. DOI = http://dx.doi.org/10.1016/0304-3975(86)90135-0
Я также предлагаю посмотреть на соответствующий документ:
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
источник
Андреас Бласс и Юрий Гуревич, Об уникальной проблеме выполнимости,
источник
Решение обеих проблем, UNIQUE SAT, а также ANOTHER SAT, с полной классификацией сложности, можно найти в статье.
Л. Джубан: теорема о дихотомии для обобщенной задачи единственной выполнимости http://link.springer.com/chapter/10.1007%2F3-540-48321-7_27
источник