En la teoría de la complejidad computacional , una rama de la ciencia de la computación , el teorema de dicotomía de Schaefer , demostrado por Thomas Jerome Schaefer , establece las condiciones necesarias y suficientes bajo las cuales un conjunto finito S de relaciones sobre el dominio booleano produce problemas de tiempo polinomial o NP-completos cuando las relaciones de S se usan para restringir algunas de las variables proposicionales . [1] Se llama teorema de dicotomía porque la complejidad del problema definido por S está en P o es NP-completo, a diferencia de una de las clases de complejidad intermedia que se sabe que existen (asumiendo P ≠ NP ) por el teorema de Ladner .
Los casos especiales del teorema de dicotomía de Schaefer incluyen la NP-completitud de SAT (el problema de satisfacibilidad booleano ) y sus dos variantes populares SAT 1-en-3 y 3SAT no todos iguales (a menudo denotadas 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.
Schaefer define un problema de decisión que él llama el problema de satisfacibilidad generalizada para S (denotado por SAT( S )), donde es un conjunto finito de relaciones sobre el dominio binario . Una instancia del problema es una S -fórmula, es decir, una conjunción de restricciones de la forma donde y son variables proposicionales. El problema es determinar si la fórmula dada es satisfacible, en otras palabras, si a las variables se les pueden asignar valores tales que satisfagan todas las restricciones dadas por las relaciones de 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 polinomial si se cumple alguna de las siguientes condiciones:
De lo contrario, el problema SAT( S ) es NP-completo.
En un artículo expositivo de Hubie Chen se ofrece una presentación moderna y simplificada del teorema de Schaefer. [3] [4] En términos modernos, el problema SAT( S ) se considera 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 dicotomía de Schaefer, el concepto más importante en álgebra universal es el de polimorfismo. Una operación es un polimorfismo de una relación si, para cualquier elección de m tuplas de R , se cumple que la tupla obtenida de estas m tuplas al aplicar f en coordenadas, es decir , está en R . Es decir, una operación f es un polimorfismo de R si R está cerrado bajo f : aplicar f a cualquier tupla en 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:
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.
Dado un conjunto Γ de relaciones, existe una conexión sorprendentemente estrecha entre sus polimorfismos y la complejidad computacional de CSP(Γ).
Una relación R se llama primitiva definible positiva , o abreviada pp-definible , 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 ) que se cumple si x , y , z no son todas iguales, y R ( x , y , z ) es x ∨ y ∨ z , entonces R puede definirse pp 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, entonces Inv ( O ) denota el conjunto de relaciones que tienen todas las operaciones en O como un polimorfismo. Pol e Inv juntos forman una conexión de Galois antitónica . Para cualquier conjunto finito Γ de relaciones sobre un dominio finito, ≪Γ≫ = Inv ( Pol (Γ)) se cumple, es decir, el conjunto de relaciones pp-definibles a partir de Γ se puede derivar de los polimorfismos de Γ. [6] Además, si Pol (Γ) ⊆ Pol (Γ') para dos conjuntos de relaciones finitos Γ 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]
El análisis se afinó posteriormente: CSP(Γ) se puede resolver en co-NLOGTIME, L-completo , NL-completo , ⊕L-completo, P-completo o NP-completo, y dado Γ, se puede decidir en tiempo polinomial cuál de estos casos se cumple. [8]
El teorema de dicotomía de Schaefer también se ha generalizado para utilizar la lógica proposicional de gráficos en lugar de la lógica booleana. [9]
Si el problema consiste en contar el número de soluciones, lo que se denota por #CSP(Γ), entonces existe un resultado similar para el dominio binario de Creignou y Hermann. [10] Específicamente, un conjunto finito de relaciones S sobre el dominio booleano define un problema de satisfacibilidad computable en tiempo polinomial si cada relación en S es equivalente a una conjunción de fórmulas afines. [2]
Para dominios mayores, Bulatov y Dalmau dieron una condición necesaria para la satisfacibilidad en tiempo polinomial. [11] Sea Γ un lenguaje de restricción finito sobre el dominio booleano. Si el problema #CSP(Γ) es computable en tiempo polinomial, entonces Γ 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 satisface Un ejemplo de una operación de Mal'tsev es la operación Minoritaria dada en la formulación algebraica moderna del teorema de dicotomía de Schaefer anterior. Por lo tanto, cuando Γ tiene la operación Minoritaria 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 sobre variables booleanas, determinadas por los valores de y . Un ejemplo de una menos simétrica es dado por . En otros dominios, como los 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 Γ es una condición insuficiente para la manejabilidad de #CSP(Γ). Sin embargo, la ausencia de un polimorfismo de Mal'tsev para Γ implica la #P-dureza de #CSP(Γ).
