En la teoría de la complejidad computacional , una rama de la informática , el teorema de la dicotomía de Schaefer establece las condiciones necesarias y suficientes bajo las cuales un conjunto finito S de relaciones sobre el dominio booleano produce problemas de tiempo polinómico o NP-completo cuando las relaciones de S se utilizan para restringir algunos de las variables proposicionales . [1] Se llama teorema de dicotomía porque la complejidad del problema definido por S está en P o NP-completo en oposición a una de las clases de complejidad intermediaque se sabe que existe (asumiendo P ≠ NP ) por el teorema de Ladner .
Los casos especiales del teorema de la dicotomía de Schaefer incluyen la completitud NP de SAT (el problema de satisfacibilidad booleano ) y sus dos variantes populares 1-en-3 SAT y no todos iguales 3SAT (a menudo denotado por NAE-3SAT). De hecho, para estas dos variantes de SAT, el teorema de dicotomía de Schaefer muestra que sus versiones monótonas (donde no se permiten negaciones de variables) también son NP-completas.
Presentación original
Schaefer define un problema de decisión que él llama problema de satisfacción generalizada para S (denotado por SAT ( S )), dondees un conjunto finito de relaciones sobre variables proposicionales. Una instancia del problema es una fórmula S , es decir, una conjunción de restricciones de la forma dónde y el son variables proposicionales. El problema es determinar si la fórmula dada es satisfiable, en otras palabras si las variables pueden ser valores tales que se satisfagan todas las restricciones como dado por las relaciones de asignar S .
Schaefer identifica seis clases de conjuntos de relaciones booleanas para las que SAT ( S ) está en P y demuestra que todos los demás conjuntos de relaciones generan un problema NP-completo. Un conjunto finito de relaciones S sobre el dominio booleano define un problema de satisfacibilidad computable en tiempo polinómico si se cumple alguna de las siguientes condiciones:
- todas las relaciones que no son constantemente falsas son verdaderas cuando todos sus argumentos son verdaderos;
- todas las relaciones que no son constantemente falsas son verdaderas cuando todos sus argumentos son falsos;
- todas las relaciones son equivalentes a una conjunción de cláusulas binarias;
- todas las relaciones son equivalentes a una conjunción de cláusulas de Horn ;
- todas las relaciones son equivalentes a una conjunción de cláusulas de cuerno dual;
- todas las relaciones son equivalentes a una conjunción de fórmulas afines. [2]
De lo contrario, el problema SAT ( S ) es NP-completo.
Presentación moderna
Hubie Chen ofrece una presentación moderna y simplificada del teorema de Schaefer en un artículo expositivo. [3] [4] En términos modernos, el problema SAT ( S ) se ve como un problema de satisfacción de restricciones sobre el dominio booleano . En esta área, es estándar denotar el conjunto de relaciones por Γ y el problema de decisión definido por Γ como CSP (Γ).
Esta comprensión moderna utiliza el álgebra, en particular, el álgebra universal . Para el teorema de la dicotomía de Schaefer, el concepto más importante del álgebra universal es el de polimorfismo. Una operación es un polimorfismo de una relación si, para cualquier elección de m tuplasde R , sostiene que la tupla obtenida de estas m tuplas aplicando f en coordenadas, es decir, Está en R . Es decir, una operación f es un polimorfismo de R si R es cerrado bajo f : aplicar f a cualquier tuplas de R produce otra tupla dentro de R . Se dice que un conjunto de relaciones Γ tiene un polimorfismo f si cada relación en Γ tiene f como polimorfismo. Esta definición permite la formulación algebraica del teorema de dicotomía de Schaefer.
Sea Γ un lenguaje de restricción finito sobre el dominio booleano. El problema CSP (Γ) es decidible en tiempo polinomial si Γ tiene una de las siguientes seis operaciones como polimorfismo:
- la operación unaria constante 0;
- la operación unaria constante 1;
- la operación binaria AND ∧;
- la operación binaria OR ∨;
- la operación de mayoría ternaria
- la operación ternaria minoritaria
De lo contrario, el problema CSP (Γ) es NP-completo.
En esta formulación, es fácil comprobar si se cumple alguna de las condiciones de manejabilidad.
Propiedades de los polimorfismos
Dado un conjunto Γ de relaciones, hay una conexión sorprendentemente estrecha entre sus polimorfismos y la complejidad computacional de CSP (Γ).
Una relación R se llama primitiva positiva definible , o breve definible por pp , a partir de un conjunto Γ de relaciones si R ( v 1 , ..., v k ) ⇔ ∃ x 1 ... x m . C se cumple para alguna conjunción C de restricciones de Γ y ecuaciones sobre las variables { v 1 , ..., v k , x 1 , ..., x m }. Por ejemplo, si Γ consiste en la relación ternaria nae ( x , y , z ) y si x , y , z no son todos iguales, y R ( x , y , z ) es x ∨ y ∨ z , entonces R puede ser pp definido por R ( x , y , z ) ⇔ ∃ a . nae (0, x , a ) ∧ nae ( y , z , ¬ a ); esta reducción se ha utilizado para demostrar que NAE-3SAT es NP-completo. El conjunto de todas las relaciones que son pp-definibles a partir de Γ se denota por ≪Γ≫. Si Γ '⊆ ≪Γ≫ para algunos conjuntos de restricciones finitos Γ y Γ', entonces CSP (Γ ') se reduce a CSP (Γ). [5]
Dado un conjunto Γ de relaciones, Pol (Γ) denota el conjunto de polimorfismos de Γ. Por el contrario, si O es un conjunto de operaciones, Inv ( O ) denota el conjunto de relaciones que tienen todas las operaciones en O como polimorfismo. Pol e Inv juntos construyen una conexión Galois . Para cualquier conjunto finito Γ de relaciones sobre un dominio finito, se cumple ≪Γ≫ = Inv (Pol (Γ)), es decir, el conjunto de relaciones pp-definibles a partir de Γ puede derivarse de los polimorfismos de Γ. [6] Además, si Pol (Γ) ⊆ Pol (Γ ') para dos conjuntos de relaciones finitas Γ y Γ', entonces Γ '⊆ ≪Γ≫ y CSP (Γ') se reduce a CSP (Γ). Como consecuencia, dos conjuntos de relaciones que tienen los mismos polimorfismos conducen a la misma complejidad computacional. [7]
Generalizaciones
El análisis se ajustó posteriormente: CSP (Γ) se puede resolver en co-NLOGTIME, L-complete , NL-complete , ⊕L-complete, P-complete o NP-complete y dado Γ, uno puede decidir en tiempo polinomial cuál de estos casos es válido. [8]
El teorema de la dicotomía de Schaefer se generalizó recientemente a una clase más amplia de relaciones. [9]
Trabajo relacionado
Si el problema es contar el número de soluciones, que se denota con #CSP (Γ), entonces se cumple un resultado similar de Creignou y Hermann. [10] Sea Γ un lenguaje de restricción finito sobre el dominio booleano. El problema #CSP (Γ) se puede calcular en tiempo polinomial si Γ tiene una operación de Mal'tsev como polimorfismo. De lo contrario, el problema #CSP (Γ) es # P-completo . Una operación de Mal'tsev m es una operación ternaria que satisfaceUn ejemplo de una operación de Mal'tsev es la operación de minoría dada en la formulación algebraica moderna del teorema de dicotomía de Schaefer anterior. Por lo tanto, cuando Γ tiene la operación Minority como polimorfismo, no solo es posible decidir CSP (Γ) en tiempo polinomial, sino también calcular #CSP (Γ) en tiempo polinomial. Hay un total de 4 operaciones de Mal'tsev en variables booleanas, determinadas por los valores de y . Un ejemplo de uno menos simétrico viene dado por. En otros dominios, como grupos, los ejemplos de operaciones de Mal'tsev incluyen y
Para dominios más grandes, incluso para un dominio de tamaño tres, la existencia de un polimorfismo de Mal'tsev para Γ ya no es una condición suficiente para la manejabilidad de #CSP (Γ). Sin embargo, la ausencia de un polimorfismo de Mal'tsev para Γ todavía implica la dureza # P de #CSP (Γ).
Ver también
- Teoremas de clasificación Max / min CSP / Ones , un conjunto similar de restricciones para problemas de optimización
Referencias
- ^ Schaefer, Thomas J. (1978). "La complejidad de los problemas de satisfacción". STOC 1978 . págs. 216–226. doi : 10.1145 / 800133.804350 .
- ↑ Schaefer (1978, p. 218 a la izquierda) define una fórmula afín de la forma x 1 ⊕ ... ⊕ x n = c , donde cada x i es una variable, c es una constante, es decir, verdadera o falsa , y "⊕" denota XOR , es decir, adición en un anillo booleano .
- ^ Chen, Hubie (diciembre de 2009). "Un encuentro de lógica, complejidad y álgebra". Encuestas de computación ACM . 42 (1): 1–32. arXiv : cs / 0611018 . doi : 10.1145 / 1592451.1592453 .
- ^ Chen, Hubie (diciembre de 2006). "Un encuentro de lógica, complejidad y álgebra". Noticias SIGACT (columna lógica) . arXiv : cs / 0611018 .
- ^ Chen (2006), p. 8, Proposición 3.9; Chen usa reducción de varios uno en tiempo polinomial
- ^ Chen (2006), p. 9, Teorema 3.13
- ^ Chen (2006), p.11, Teorema 3.15
- ^ Allender, Eric; Bauland, Michael; Immerman, Neil; Schnoor, Henning; Vollmer, Heribert (junio de 2009). "La complejidad de los problemas de satisfacibilidad: refinando el teorema de Schaefer" (PDF) . Revista de Ciencias de la Computación y Sistemas . 75 (4): 245-254. doi : 10.1016 / j.jcss.2008.11.001 . Consultado el 19 de septiembre de 2013 .
- ^ Bodirsky, Manuel; Pinsker, Michael (2015). "Teorema de Schaefer para gráficos". J. ACM . 62 (3): 19: 1–19: 52. arXiv : 1011.2894 . doi : 10.1145 / 2764899 .
- ^ Creignou, Nadia; Hermann, Miki (1996). "Complejidad de los problemas de conteo de satisfacibilidad generalizada". Información y Computación . 125 (1): 1–12. doi : 10.1006 / inco.1996.0016 . ISSN 0890-5401 .