Este problema es co-NP-completo. Está en co-NP porque un DNF tautológico es solo la negación de un CNF insatisfactorio y co-3SAT es un problema co-NP-completo que determina si un CNF es insatisfactorio.
Aquí hay una reducción de co-3SAT para mostrar que es co-NP-hard. Comience con una instancia de co-3SAT. Agregue dos nuevas cláusulas, [math] x [/ math] y [math] \ bar {x} [/ math] donde [math] x [/ math] es una nueva variable que no está en la instancia original. Esto definitivamente es insatisfactorio, por lo que su negación es un DNF tautológico. Si agregamos una nueva variable [math] v [/ math] a la cláusula que contiene solo [math] x [/ math], las últimas dos cláusulas se convierten en [math] x \ wedge v [/ math] y [math] \ bar {x} [/ matemáticas].
Estas cláusulas satisfacen la fórmula si [math] x [/ math] es falso o [math] v [/ math] es verdadero, dejando solo el caso donde [math] x [/ math] es verdadero y [math] v [/ matemáticas] es falso. Como [math] x [/ math] y [math] v [/ math] no aparecen en el resto del DNF, todos estos casos son satisfactorios si y solo si el DNF restante es una tautología, que es equivalente a la El CNF original es insatisfactorio. Por lo tanto, el DNF que producimos sigue siendo una tautología si y solo si la instancia original de co-3SAT no era satisfactoria. Esto finaliza la prueba de que este problema es co-3SAT-complete.
- ¿Cuándo requerimos hacer una transformación no lineal o reducción de dimensiones como el kernel PCA?
- ¿Todas las integrales pueden ser calculadas por una computadora? Del mismo modo, ¿hay integrales en este momento que los matemáticos no puedan resolver?
- ¿Cuál es la mejor manera de aprender el aprendizaje automático aprovechando mi sólida formación matemática?
- Mi cerebro no procesa muy bien la resolución de problemas matemáticos. ¿La programación es para mí?
- ¿Cómo sabe la CPU que estamos usando el complemento de uno o el complemento de dos para representar números negativos?
Debido a que esto es co-3SAT-complete, saber que está en PTIME implicaría que P = NP. Por lo tanto, no sabemos si está en PTIME y la mayoría de la gente cree que no está en PTIME.
