Satisfacibilidad 3 no todos iguales

En complejidad computacional , la 3-satisfacibilidad no-totalmente-igual ( NAE3SAT ) es una variante NP-completa del problema de satisfacibilidad booleana , que se utiliza a menudo en pruebas de NP-completitud. ^{[ 1 ]}

Al igual que en la 3-satisfacibilidad , una instancia del problema consiste en una colección de variables booleanas y una colección de cláusulas, cada una de las cuales combina tres variables o negaciones de variables. Sin embargo, a diferencia de la 3-satisfacibilidad, que requiere que cada cláusula tenga al menos un valor booleano verdadero, NAE3SAT requiere que los tres valores de cada cláusula no sean todos iguales entre sí (es decir, al menos uno es verdadero y al menos uno es falso). ^{[ 2 ]}

La NP-completitud de NAE3SAT se puede demostrar mediante una reducción a partir de la 3-satisfacibilidad (3SAT). ^{[ 2 ]} Primero, el 3SAT no simétrico se reduce al NAE4SAT simétrico añadiendo un literal ficticio común.${\displaystyle s}$a cada cláusula, entonces NAE4SAT se reduce a NAE3SAT dividiendo las cláusulas como en la reducción de general${\displaystyle k}$-satisfacción con 3SAT.

En detalle, una instancia de 3SAT${\displaystyle \Phi =\bigwedge _{i=1}^{m}(l_{i,1}\vee l_{i,2}\vee l_{i,3})}$(donde el${\displaystyle l_{i,j}}$son literales arbitrarios) se reduce a la instancia NAE4SAT${\displaystyle \Psi =\bigwedge _{i=1}^{m}\operatorname {NAE} (l_{i,1},l_{i,2},l_{i,3},s)}$dónde${\displaystyle s}$es una nueva variable. Una asignación satisfactoria para${\displaystyle \Phi }$se convierte en una tarea satisfactoria para${\displaystyle \Psi }$al establecer${\displaystyle s=0}$Por el contrario, una tarea satisfactoria con${\displaystyle s=0}$para${\displaystyle \Psi }$debe tener al menos otro literal verdadero en cada cláusula y por lo tanto ser una asignación satisfactoria para${\displaystyle \Phi }$. Finalmente, una tarea satisfactoria con${\displaystyle s=1}$para${\displaystyle \Psi }$puede debido a la simetría de${\displaystyle 0}$y${\displaystyle 1}$ser volteado para producir una tarea satisfactoria con${\displaystyle s=0}$.

NAE3SAT sigue siendo NP-completo cuando todas las cláusulas son monótonas (lo que significa que las variables nunca se niegan), según el teorema de dicotomía de Schaefer . ^{[ 3 ]} NAE3SAT monótono también puede interpretarse como una instancia del problema de división de conjuntos , o como una generalización de la prueba de bipartición de grafos a hipergrafos 3-uniformes : pregunta si los vértices de un hipergrafo pueden colorearse con dos colores de manera que ninguna hiperarista sea monocromática. Más fuertemente, es NP-difícil encontrar coloraciones de hipergrafos 3-uniformes con cualquier número constante de colores, incluso cuando existe una 2-coloración. ^{[ 4 ]}

A diferencia de 3SAT, algunas variantes de NAE3SAT en las que los grafos que representan la estructura de variables y cláusulas son grafos planares pueden resolverse en tiempo polinomial . En particular, esto es cierto cuando existe un grafo planar con un vértice por variable, un vértice por cláusula, una arista para cada incidencia variable-cláusula y un ciclo de aristas que conecta todos los vértices de las variables. ^{[ 5 ]}