Weryfikacja unikalnych rozwiązań SAT

Rozważ następujący problem: biorąc pod uwagę formułę CNF i zadanie spełniające tę formułę, czy istnieje inne zadowalające przypisanie dla tej formuły?

Jaka jest złożoność tego problemu? (Z pewnością jest w NP, ale czy to jest NP-trudne?)

Co się stanie, jeśli nie otrzymasz zadania i chcesz po prostu zdecydować, czy formuła ma unikalne, satysfakcjonujące zadanie?

Dzięki.

Problem decydowania o tym, czy dana formuła CNF ma zadowalające przypisanie inne niż dana, można łatwo wykazać jako NP-zupełny, przekształcając formułę CNF w celu dodania jednego trywialnego rozwiązania. Problem ten nazywa się „Innym problemem rozwiązania (ASP) SAT” w [YS03], gdzie służy do systematycznego dowodzenia, że ​​(wersje decyzyjne) ASP wielu innych problemów są również NP-kompletne.

Problem decydowania o tym, czy dana formuła CNF ma unikalne, satysfakcjonujące przypisanie, czy nie (więc musisz odpowiedzieć „nie”, jeśli formuła nie ma zadowalających przypisań lub więcej niż jednego zadowalającego przypisania), ma charakter amerykański . US zawiera zarówno UP, jak i coNP .

Referencje

[YS03] Takayuki Yato i Takahiro Seta. Złożoność i kompletność znalezienia innego rozwiązania i jego zastosowania do zagadek. Transakcje IEICE dotyczące podstaw elektroniki, komunikacji i informatyki, E86-A (5): 1052–1060, maj 2003 r.

Edycja : wcześniejsza wersja (wersja 1) tej odpowiedzi zawierała pomyłkę między wersją decyzyjną a wersją wyszukiwania. Zostało to naprawione.

Pamiętam, jak Yoram Moses i ja studiowali ten problem w połowie lat 80. (w świetle niektórych zastosowań) i odkrywając, że dla wielu naturalnych problemów NPC problemem znalezienia drugiego / alternatywnego rozwiązania (lub podjęcia decyzji, czy takie istnieje) jest NPC. Potem dowiedzieliśmy się, że to było znane, ale nie pamiętam referencji i nie udało nam się znaleźć takiego (tj. Wcześniejszego niż połowa lat 80.). Ale jestem pewien, że dobrze pamiętam powyższe.

Tylko komentarz do Ryana. Fakt, że twierdzenie można podać jako ćwiczenie w obecnych klasach, nie czyni go mniej atrakcyjnym. Powinien był zostać opublikowany w artykule z odpowiednim tytułem w momencie jego odkrycia ...

Oded Goldreich

Tutaj piszę fragment następującej pracy:

Valiant, LG i Vazirani, VV 1986. NP jest tak łatwe, jak wykrywanie unikalnych rozwiązań. Teoria Comput. Sci. 47, 1 (listopad 1986), 85-93. DOI = http://dx.doi.org/10.1016/0304-3975(86)90135-0

Dla każdego znanego problemu NP-zupełnego liczba rozwiązań jego instancji zmienia się w szerokim zakresie, od zera do wykładniczo wielu. Naturalne jest zatem pytanie, czy nieodłączna trudność problemu NP-zupełnego jest spowodowana tą szeroką zmiennością. Udzielamy negatywnej odpowiedzi na to pytanie, stosując pojęcie losowej wielomianowej redukcji czasu. Pokazujemy, że problemy z rozróżnieniem między instancjami SAT mającymi zero lub jedno rozwiązanie, lub ze znalezieniem rozwiązań dla instancji SAT posiadających unikalne rozwiązanie, są tak trudne jak SAT, przy losowych redukcjach.

Proponuję również zajrzeć do odpowiedniego dokumentu:

Beigel, R., Buhrman, H., i Fortnow, L. 1998. NP może nie być tak łatwe jak wykrywanie unikalnych rozwiązań. W Proceedings z trzydziestego dorocznego sympozjum ACM na temat teorii komputerów (Dallas, Teksas, Stany Zjednoczone, 24–26 maja 1998 r.). STOC '98. ACM, Nowy Jork, Nowy Jork, 203-208. DOI = http://doi.acm.org/10.1145/276698.276737

Pierwszy problem to NP-zupełny, a drugi to problem Unikalnej satyfikowalności, który jest Co-NP-twardy i jego klasa (przecięcie zbioru NP z zestawem Co-NP).$DP=\{(L_1 ∩ L_2)| L_1 \in NP, L_2\in CoNP\}$

Andreas Blass i Yuri Gurevich, W sprawie wyjątkowego problemu satysfakcji,

Rozwiązanie obu problemów, UNIQUE SAT oraz ANOTHER SAT, z pełną klasyfikacją złożoności, można znaleźć w artykule

L. Juban: Twierdzenie o dychotomii uogólnionego unikalnego problemu satysfakcji http://link.springer.com/chapter/10.1007%2F3-540-48321-7_27