¿Por qué está 2SAT en P?

55

Me he encontrado con el algoritmo polinómico que resuelve 2SAT. Me ha parecido sorprendente que 2SAT esté en P, donde todas (o muchas otras) de las instancias de SAT son NP-Complete. ¿Qué hace que este problema sea diferente? ¿Qué lo hace tan fácil (NL-Complete, incluso más fácil que P)?

Chico
fuente
18
¿Por qué la gente piensa que esta es una pregunta tan mala?
Peter Shor
12
Un aspecto interesante es que si desea conocer el número máximo de cláusulas simultáneamente satisfactorias en una expresión 2SAT (es decir, Max2SAT), volverá a NP-complete nuevamente.
Shaun Harker
11
Esta es una pregunta horrible, porque no tiene una respuesta útil, o una pregunta fantástica, porque la única respuesta correcta es "nadie lo sabe".
Jeffε
12
Lea el documento "La complejidad de los problemas de satisfacción: refinando el teorema de Schaefer".
Diego de Estrada
3
Estimado Guy, el hecho de que 2SAT está en P está cubierto en casi todos los libros de texto de complejidad estándar, por lo que cuando dices que acabas de notar este hecho, la pregunta parece que ni siquiera has leído un libro de texto estándar en complejidad.
Kaveh

Respuestas:

88

Aquí hay una explicación más intuitiva y sin pretensiones en la línea de la respuesta de MGwynne.

Con -SAT, solo puede expresar implicaciones de la forma , donde y son literales. Más precisamente, cada cláusula l_1 puede entenderse como un par de implicaciones: y . Si se establece true, debe ser cierto también. Si establece en falso, debe ser falso. Tales implicaciones son sencillas: no hay elección, solo tiene2abab2l1l2¬l1l2¬l2l1abba1posibilidad, no hay espacio para la multiplicación de casos. Que sólo puede seguir todas las posibles implicaciones de la cadena, y ver si alguna vez deriva tanto de y de : si lo hace por alguna , entonces la fórmula 2-SAT es insaciable, de lo contrario es satisfiable. Es el caso de que el número de posibles cadenas de implicación está polinómicamente limitado en el tamaño de la fórmula de entrada.¬lll¬ll

Con -SAT, se puede expresar implicaciones de la forma , donde , y son literales. Ahora usted está en problemas: si se establece true, entonces o bien o debe ser cierto, pero ¿cuál? Tienes que elegir: tienes 2 posibilidades. Aquí es donde la multiplicación de casos se hace posible, y donde surge la explosión combinatoria.3abcabcabc

En otras palabras, -SAT puede expresar la presencia de más de una posibilidad, mientras que -SAT no tiene esa capacidad. Es precisamente esa presencia de más de una posibilidad ( posibilidades en el caso de -SAT, posibilidades en el caso de -SAT) lo que causa la explosión combinatoria típica de problemas NP-completos.3223k1k

Giorgio Camerani
fuente
66
¡Ojalá pudiera votar esto más! ¡Una respuesta mucho mejor!
MGwynne
55
@MGwynne: Gracias por su amable comentario. De nada, ¡y su respuesta es realmente muy buena!
Giorgio Camerani
8
Esta es una buena respuesta a una buena pregunta (en mi humilde opinión). Como Mac Lane ha escrito: "Los matemáticos introducen manipulaciones formales efectivas o engañosas que sin duda tienen una idea rectora, pero es más fácil establecer las manipulaciones que formular la idea en palabras ... Una exposición perspicaz de una pieza of Mathematics permite que las ideas brillen a través de la exhibición de manipulaciones ". Esta pregunta y respuesta en particular ayudó a "las ideas a brillar" (para mí). ¡Gracias! :)
John Sidles
44
@ John: ¡De nada! ;-) Muchas gracias por su gran y generoso comentario, realmente lo aprecio. No podría estar más de acuerdo con las palabras de Mac Lane.
Giorgio Camerani
De acuerdo con la respuesta de Giorgio Camerani, no vale la pena reducir cualquier problema de NP a 3SAT si introduce más variables booleanas ficticias, tiene más cláusulas y no tiene ganancia ni ganancia, pero es más preferible reducirlo a CNF SAT o satisfacción booleana o Circuito SAT en su lugar, porque en estos problemas tiene variables booleanas menores y cláusulas menores y eso significa que los algoritmos ingenuos de fuerza bruta, los mapas de Karnaugh y el algoritmo Quine-McClusky tienen una mayor complejidad: D.
Despedida Stack Exchange
31

Considere la resolución en una fórmula 2-SAT. Cualquier resolución es de tamaño máximo 2 (tenga en cuenta que si para cláusulas de longitud y resp). El número de cláusulas de tamaño 2 es cuadrático en el número de variables. Por lo tanto, el algoritmo de resolución está en P.n+m22n,m2nm

Una vez que llegue a 3-SAT, puede obtener solventes cada vez más grandes, por lo que todo tiene forma de pera :).

Intenta traducir un problema a 2-SAT. Como no puede tener cláusulas de tamaño 3, no puede (en general) codificar implicaciones que involucren 3 variables o más, por ejemplo, que una variable es el resultado de una operación binaria en otras dos. Esta es una gran restricción.

MGwynne
fuente
3
"No se pueden codificar cosas como implicación" - IMP-SAT también está en P (y creo que NL)
Max
8
¬ p qpq es simplemente . ¬pq
Kaveh
1
Kaveh, buen punto, arreglado ahora.
MGwynne
Como ya dije cuando redujo su problema arbitrario de NP a Satisfacción Booleana o Circuito SAT o CNF SAT, no reduzca el problema a 3SAT, porque el problema se vuelve aún más difícil y complejo con más variables y cláusulas booleanas. ¡Incluso el algoritmo de resolución se vuelve menos eficiente en el nuevo problema!
Farewell Stack Exchange
20

Como dice Walter, las cláusulas de 2-SAT tienen una forma especial. Esto puede ser explotado para encontrar soluciones rápidamente.

En realidad, hay varias clases de instancias SAT que se pueden decidir en tiempo polinómico, y 2-SAT es solo una de estas clases manejables . Hay tres tipos generales de razones para la trazabilidad:

  1. (Trazabilidad estructural) Cualquier clase de instancias SAT en las que las variables interactúen en forma de árbol se puede resolver en tiempo polinómico. El grado del polinomio depende del ancho máximo de instancias en la clase, donde el ancho mide qué tan lejos está una instancia de ser un árbol. Más precisamente, Marx demostró que si las instancias tienen un ancho submodular limitado, entonces la clase se puede decidir en tiempo polinomial utilizando un enfoque de divide y vencerás.

  2. (Trazabilidad del lenguaje) Cualquier clase de instancias SAT donde el patrón de variables verdadero-falso es "agradable", puede resolverse en tiempo polinómico. Más precisamente, el patrón de literales define un lenguaje de relaciones, y Schaefer clasificó los seis idiomas que conducen a la trazabilidad, cada uno con su propio algoritmo. 2-SAT forma una de las seis clases de Schaefer.

  3. (Trazabilidad híbrida) También hay algunas clases de instancias que no se incluyen en las otras dos categorías, pero que pueden resolverse en tiempo polinómico por otras razones.

    • Dániel Marx, Propiedades de hipergrafía manejable para satisfacción de restricciones y consultas conjuntas , STOC 2010. ( doi , preprint )
    • Thomas J. Schaefer, La complejidad de los problemas de satisfacción , STOC 1978. ( doi )
András Salamon
fuente
2
También hay argumentos basados ​​en la estructura del espacio de solución de la literatura aleatoria de k-SAT que pueden usarse para explicar la diferencia.
Kaveh
3
@Kaveh: se suponía que mi descripción de la trazabilidad híbrida era lo suficientemente vaga como para abarcar tales cosas. Por ejemplo, para tipos de instancias muy especiales, uno puede argumentar a favor de la satisfacción basándose en el Lema local de Lovász. Vea la encuesta de 1997 de Pearson y Jeavons: cs.ox.ac.uk/publications/publication1610-abstract.html
András Salamon
3
También tenga en cuenta que SAT es el caso especial del problema de satisfacción de restricciones donde cada variable puede tomar 2 valores. Cuando las variables pueden tomar 3 valores, hay 10 clases de idiomas manejables, clasificadas por Andrei Bulatov: cs.sfu.ca/~abulatov/papers/3-el-journal.ps Las clases híbridas también son más interesantes para dominios más grandes.
András Salamon
10

Si comprende el algoritmo para 2SAT, ya sabe por qué está en P: esto es precisamente lo que demuestra el algoritmo. Creo que este cómic ilustra mi punto. Como ya sabe por qué 2SAT está en P, lo que probablemente quiera saber es por qué 2SAT no es NP-hard.

Para comprender por qué 2SAT no es NP-hard, debe tener en cuenta lo fácil que es reducir otros problemas en NP. Para obtener una comprensión intuitiva de esto, observe cómo SAT puede reducirse a 3SAT e intente aplicar las mismas técnicas para reducir SAT a 2SAT. 2SAT no es tan expresivo como 3SAT y otras variantes de SAT.

Dave
fuente