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.
Odpowiedzi:
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.
źródło
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
źródło
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
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
źródło
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={(L1∩L2)|L1∈NP,L2∈CoNP}
Andreas Blass i Yuri Gurevich, W sprawie wyjątkowego problemu satysfakcji,
źródło
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
źródło