El problema 3-SAT y 2-SAT son
(A) ambos en P
(B) ambos NP completos
(C) NP-completos y en P respectivamente
(D) indecidibles y NP-completos respectivamente
Respuesta: (C)
Explicación: El problema booleano de satisfacibilidad (SAT) es un problema de decisión, cuya instancia es una expresión booleana escrita usando solo AND, OR, NOT, variables y paréntesis. El problema es: dada la expresión, ¿hay alguna asignación de valores VERDADERO y FALSO a las variables que harán que toda la expresión sea verdadera? Se dice que una fórmula de lógica proposicional es satisfactoria si se pueden asignar valores lógicos a sus variables de manera que la fórmula sea verdadera.
3-SAT y 2-SAT son casos especiales de k-satisfactibilidad (k-SAT) o simplemente satisfacibilidad (SAT), cuando cada cláusula contiene exactamente k = 3 yk = 2 literales respectivamente.
2-SAT es P mientras que 3-SAT es NP Completo. (Ver esto para una explicación)
Referencias:
http://en.wikipedia.org/wiki/Boolean_satisfiability_problem
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA