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?
źródło
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.
źródło