Considere el problema de decisión 2CNFSAT definido como sigue:
(A) NP-Completo.
(B) resoluble en tiempo polinomial por reducción a la accesibilidad del gráfico dirigido.
(C) solucionable en tiempo constante ya que cualquier instancia de entrada es satisfactoria.
(D) NP-duro, pero no NP-completo.
Respuesta: (B)
Explicación: 2CNF-SAT se puede reducir a un problema de componentes fuertemente conectados. Y el componente fuertemente conectado tiene una solución en tiempo polinomial. Por lo tanto, 2CNF-SAT es soluble en tiempo polinomial. Consulte https://en.wikipedia.org/wiki/2-satisfiability#Strongly_connected_components para obtener más información.
Como nota al margen, 3CNFSAT es un problema NP completo.
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