Clasificación de satisfacibilidad problema intratable / tratables variantes

Question

Recientemente me encontré en un papel [1] una versión simétrica especial de SAT denomina 2/2 / 4-SAT . Pero hay muchos $ \ text {NP} $ - variantes completas por ahí, por ejemplo: MONOTONO NAE-3SAT , MONOTONO 1-IN-3SAT , .. .

Algunas otras variantes son tratables: $ 2 $ - $ \ text {SAT} $, planar-NAE - $ \ text {SAT} $, ...

¿Hay documentos de la encuesta (o páginas web) que clasifican todas la (raro) $ \ text {SAT} variantes $ que han demostrado ser $ \ text {NP} $ - completa (o en $ \ text {P } $)?

---

1. encontrar una solución más corto para el $ N $ x $ N $ extensión del 15-Puzzle es intratable por D. Ratner y M. Warmuth (1986)

Answer 1

Classic, los resultados conocidos

Como se ha mencionado por Standa Zivny sobre la cuestión relacionada de CSTheory, problemas que son fáciles SAT ? , hay una consecuencia bien conocida por Schaefer a partir de 1978 (citando la respuesta de Zivny):

Si SAT está parametrizada por un conjunto de relaciones permitidos en cualquier instancia, a continuación, sólo hay 6 casos tratables: 2-SAT (es decir, cada cláusula es binario), Horn-SAT, dual-Horn-SAT, affine-SAT ( soluciones a las ecuaciones lineales en GF (2)), 0-válidos (relaciones satisfechas por la asignación todo-0) y 1-válidos (relaciones satisfechas por la asignación todo-1).

planar-3SAT es decir, la versión plana de 3SAT se sabe que es \ mathcal {NP} $ $ - completa. Ver D Lichtenstein, fórmulas planas y sus usos, 1981 . La versión no plana de 3SAT es por supuesto el $ clásica muy conocida \ mathcal {NP} $ -. Problema completo

No-All-Igualdad 3SAT ( NAE-3SAT ) es $ \ mathcal {NP} $ - completa. Sin embargo, la versión plana de ella está en $ \ mathcal {P} $, como se muestra por Moret, planar NAE3SAT está en P, 1988 .

Más reciente y / o "raro" variantes

$ k $ -colourable Monótono NAE-3SAT

Aquí hay una variante más exótico o extraño, un problema de decisión llamado $ k $ -colourable Monótono NAE-3SAT

Dado un monótono expresión CNF $ \ $ phi con exactamente tres variables distintas en cada cláusula, tal que el grafo de restricciones correspondiente $ G (\ phi) $ es k-coloreable, es la expresión $ \ phi $ no-todo- satisfiable iguales?

Aquí el correspondiente gráfico de restricción de $ G (\ phi) $ es un simple grafo no dirigido asociada con $ \ phi $ como sigue: Cada variable de $ \ phi $ es un vértice en $ G $, y dos vértices tener una ventaja entre ellos si y sólo si aparecen en alguna cláusula juntos.

Por $ k = 4 $ el problema está en $ \ mathcal {P} $. Para k = $ 5 $ sin embargo, es $ \ mathcal {NP} $ - completa. Ver P Jain, En una variante del Monótono-NAE 3SAT y el problema Triángulo de corte libre, 2010 .

Linear CNF variantes

Aunque no es quizás ser exótico o raro, algunas variantes conocidas, a saber NAE-SAT (no-all-igual SAT) y XSAT (SAT exacta; < em> exactamente un literal en cada cláusula a 1 y todos los demás literales a 0), del problema satisfacibilidad han sido investigados en el entorno linear . Cláusulas de una fórmula pairwise lineal tienen al más variable uno en común. Curiosamente, el estado de la complejidad no se deduce del teorema de Schaefer.

NAE-SAT y XSAT permanecerá $ \ mathcal {NP} $ - completa cuando se está restringido a las fórmulas lineales. Por otra parte, NAE-SAT y XSAT son todavía $ \ mathcal {NP} $ - completa sobre las fórmulas solamente contienen cláusulas de longitud al menos $ k $, para cada entero positivo fijo $ k \ geq 3 $. Son $ \ mathcal {NP} $ - completa para monótona (no literales positivos) lineal fórmulas. Sin embargo, NAE-SAT es en tiempo polinómico decidable en fórmulas lineales exactas, donde cada par de cláusulas distintas tiene exactamente una variable en común.

Algunos aspectos adicionales relativos a la complejidad de NAE-SAT y XSAT bajo ciertas suposiciones son probablemente todavía abierta. Para más detalles, véase, por ejemplo Porschen y Schmidt, en algún SAT-Variantes más lineal Fórmulas de 2009 y Porschen et al., La complejidad Resultados para Linear XSAT-Problemas, 2010 .