En la teoría de la complejidad computacional , una rama de la informática , el teorema de dicotomía de Schaefer , demostrado por Thomas Jerome Schaefer , establece 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 utilizan 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 Teorema de Ladner .
Los casos especiales del teorema de dicotomía de Schaefer incluyen la integridad 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 como 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 al que llama problema de satisfacción generalizada para S (denotado por SAT( S )), donde es un conjunto finito de relaciones en el dominio binario . Un ejemplo del problema es una fórmula S , 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 satisfactoria, 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 cuales 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:
De lo contrario, el problema SAT( S ) es NP-completo.
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 considera un problema de satisfacción de restricciones en 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 aplicando 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 restricciones finitas 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 positiva definible , o corta pp-definible , a partir de un conjunto Γ de relaciones si R ( v 1 , ... , v k ) ⇔ ∃ x 1 ... x m . C es válido 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 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 finitas Γ 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 en antitono . 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 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]
Posteriormente, el análisis se ajustó: CSP(Γ) se puede resolver en co-NLOGTIME, L-completo , NL-completo , ⊕L-completo, P-completo o NP-completo, y dado Γ, se puede decidir en polinomio tiempo cuál de estos casos se cumple. [8]
El teorema de dicotomía de Schaefer también se ha generalizado para utilizar lógica proposicional de gráficos en lugar de lógica booleana. [9]
Si el problema es contar el número de soluciones, que se denota por #CSP(Γ), entonces Creignou y Hermann obtienen un resultado similar para el dominio binario. [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 más grandes, Bulatov y Dalmau dieron una condición necesaria para la satisfacibilidad en tiempo polinomial. [11] Sea Γ un lenguaje de restricción finita sobre el dominio booleano. Si el problema #CSP(Γ) es computable en tiempo polinómico, 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 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 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 uno menos simétrico lo da . En otros dominios, como grupos , 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 dureza #P de #CSP(Γ).
