Weryfikacja unikalnych rozwiązań SAT

25

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.

JOT--
źródło
13
Twój pierwszy problem to często zadanie domowe. Wskazówka: biorąc pod uwagę dowolną formułę F, zaprojektuj formułę F ', w której przypisanie zerowe spełnia ją w sposób trywialny, i istnieje drugie zadowalające przypisanie F' iff F jest zadowalające.
Ryan Williams
1
@ Hsien-Chih Chang, mieliśmy nazwisko Odeda na pierwszej stronie przed twoją poprawką, ponowne tagowanie nie jest pilne, byłoby miło, gdyby jego nazwisko pozostało tam trochę dłużej. :)
Kaveh
1
@Kaveh: Ups, przepraszam. Wydaje mi się, że jakoś zakładam, że zostanie i będzie udzielał coraz więcej dobrych odpowiedzi, więc jego nazwisko będzie często pojawiać się na stronie głównej :)
Hsien-Chih Chang 之 之
@ Hsien-Chih Chang, też mam taką nadzieję. :)
Kaveh

Odpowiedzi:

27

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.

Tsuyoshi Ito
źródło
6
Tylko uwaga: kompletność NP „innego problemu rozwiązania” to folklor znany na długo przed 2003 rokiem. (Być może istnieje wzmianka z lat siedemdziesiątych, ale dowód jest tak łatwy, że w to wątpię.)
Ryan Williams,
@Ryan: Dziękuję za notatkę. Zredagowałem odpowiedź, aby wyjaśnić związek z [YS03].
Tsuyoshi Ito
22

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

Oded Goldreich
źródło
15
Hej, witaj na pokładzie! Tak się cieszę, że cię tu widzę :)
MS Dousti,
12

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

MS Dousti
źródło
6

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={(L1L2)|L1NP,L2CoNP}

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

Mohammad Al-Turkistany
źródło
1
Drobna uwaga: drugi problem nie jest problemem obietnicy.
Tsuyoshi Ito
1
Zrozumiałem to i naprawiłem, ale i tak dziękuję za wykrycie!
Tsuyoshi Ito
6
Nawiasem mówiąc, nie skopiowałem niczego z twojej odpowiedzi, więc nie mam pojęcia, do czego odnosi się twój komentarz: „Kiedy kopiujesz z innej odpowiedzi, proszę to zaznaczyć”. Skopiowałem odniesienie do mojej odpowiedzi z innego mojego postu na MathOverflow ( mathoverflow.net/questions/31251/... ), ale nie sądzę, że masz na myśli to.
Tsuyoshi Ito