Jaki jest przykład niezadowalającej formuły 3-CNF?

15

Próbuję owinąć głowę wokół dowodu kompletności NP, który wydaje się obracać wokół SAT / 3CNF-SAT.

Może jest późna godzina, ale obawiam się, że nie mogę wymyślić formuły 3CNF, której nie można spełnić (prawdopodobnie brakuje mi czegoś oczywistego).

Czy możesz podać mi przykład takiej formuły?

użytkownik11171
źródło

Odpowiedzi:

29

Technicznie rzecz biorąc, możesz zapisać w 3-CNF jako ( x x x ) ( ¬ x ¬ x ¬ x ) , ale prawdopodobnie potrzebujesz „prawdziwego” przykładu.x¬x(xxx)(¬x¬x¬x)

W takim przypadku formuła 3CNF wymaga co najmniej 3 zmiennych. Ponieważ każda klauzula wyklucza dokładnie jedno zadanie, oznacza to, że potrzebujesz co najmniej klauzul, aby mieć niezadowalającą formułę. Rzeczywiście najprostszy to:2)3)=8

Nietrudno dostrzec, że ta formuła jest niedopasowana.

(xyz)(xy¬z)(x¬yz)(x¬y¬z)(¬xyz)(¬xy¬z)(¬x¬yz)(¬x¬y¬z)
Shaull
źródło
być może jestem tu dość naiwny, ale dlaczego nie możesz wykonać serii porównań, aby ustalić, czy istnieją zestawy v wyrażeń nie równoważnych? - v to liczba unikalnych zmiennych. Jeśli poprawnie policzyłem, jest tylko n ( n - 1 )2)vvn(n-1)2)
@BenCrossley - nie jestem pewien, co masz na myśli. Czy możesz podać przykład?
Shaull