Los problemas 3-SAT y 2-SAT son
(A) Ambos NP-completos
(B) Ambos en P
(C) NP-completos y en P, respectivamente
(D) Indecidibles y NP-completos, respectivamente
Respuesta: (C)
Explicación : El problema 3-SAT es un problema completo NP, mientras que el problema 2-SAT es un problema de clase P.
Consulte: 2-Satisfacción (2-SAT) Problema La
opción (C) es correcta.
Cuestionario de esta pregunta
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