Estoy tratando de entender una prueba de integridad de NP que parece girar en torno a SAT / 3CNF-SAT.
Tal vez sea tarde, pero me temo que no puedo pensar en una fórmula 3CNF que no pueda satisfacerse (probablemente me falta algo obvio).
¿Me puede dar un ejemplo para tal fórmula?
logic
satisfiability
3-sat
usuario11171
fuente
fuente
Si desea ejemplos más complejos de tales fórmulas, eche un vistazo a algunos problemas de referencia de SATLIB . ToughSAT también es una buena herramienta para crear instancias 3-SAT; Es fácil construir instancias satisfactorias e insatisfactorias.
fuente