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?

logic satisfiability 3-sat

— użytkownik11171
źródło

29

Technicznie rzecz biorąc, możesz zapisać w 3-CNF jako , ale prawdopodobnie potrzebujesz „prawdziwego” przykładu. $x\wedge \neg x$ $(x\vee x\vee x)\wedge (\neg x\vee \neg x\vee \neg 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.

(x \lor y \lor z) \land (x \lor y \lor \neg z) \land (x \lor \neg y \lor z) \land (x \lor \neg y \lor \neg z) \land (\neg x \lor y \lor z) \land (\neg x \lor y \lor \neg z) \land (\neg x \lor \neg y \lor z) \land (\neg x \lor \neg y \lor \neg z)

$(x\vee y\vee z)\wedge (x\vee y\vee \neg z)\wedge (x\vee \neg y\vee z)\wedge(x\vee \neg y\vee \neg z)\wedge(\neg x\vee y\vee z)\wedge(\neg x\vee y\vee \neg z)\wedge(\neg x\vee \neg y\vee z)\wedge(\neg x\vee \neg y\vee \neg 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

wyrażeń nie równoważnych? -

to liczba unikalnych zmiennych. Jeśli poprawnie policzyłem, jest tylko

2^{v}

$2^v$

v

$v$

\frac{n (n - 1)}{2}

$\frac{n(n-1)}{2}$

@BenCrossley - nie jestem pewien, co masz na myśli. Czy możesz podać przykład?

— Shaull

8

Jeśli chcesz bardziej złożonych przykładów takich formuł, zapoznaj się z niektórymi problemami z testami porównawczymi SATLIB . ToughSAT jest także dobrym narzędziem do tworzenia instancji 3-SAT; łatwo jest tworzyć zarówno satysfakcjonujące, jak i niezadowalające instancje.

— Juho
źródło