Teorema de la dicotomía de Schaefer

En la teoría de la complejidad computacional , una rama de la informática , el teorema de la 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 la dicotomía porque la complejidad del problema definido por S está en P o es NP-completo, en contraposición a una de las clases de complejidad intermedia que se sabe que existen (suponiendo P ≠ NP ) por el teorema de Ladner .

Entre los casos especiales del teorema de dicotomía de Schaefer se incluye la NP-completitud del SAT (el problema de satisfacibilidad booleana ) y sus dos variantes más populares: el SAT 1 en 3 y el SAT 3 no todos iguales (a menudo denominado NAE-3SAT). De hecho, para estas dos variantes del SAT, el teorema de dicotomía de Schaefer demuestra que sus versiones monótonas (en las que no se permiten negaciones de variables) también son NP-completas.

Schaefer define un problema de decisión que denomina problema de satisfacibilidad generalizada para S (denotado por SAT( S )), donde${\displaystyle S=\{R_{1},\ldots ,R_{m}\}}$es un conjunto finito de relaciones sobre el dominio binario${\displaystyle \{0,1\}}$. Un ejemplo del problema es una fórmula S , es decir, una conjunción de restricciones de la forma${\displaystyle R_{j}(x_{i_{1}},\dots ,x_{i_{n}})}$dónde${\displaystyle R_{j}\in S}$y el${\displaystyle x_{i_{j}}}$son variables proposicionales. El problema consiste en determinar si la fórmula dada es satisfacible, es decir , si a las variables se les pueden asignar valores de tal manera 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 ) pertenece a 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:

1. Todas las relaciones que no son constantemente falsas son verdaderas cuando todos sus argumentos son verdaderos;
2. Todas las relaciones que no son constantemente falsas son verdaderas cuando todos sus argumentos son falsos;
3. Todas las relaciones son equivalentes a una conjunción de cláusulas binarias ;
4. Todas las relaciones son equivalentes a una conjunción de cláusulas de Horn ;
5. Todas las relaciones son equivalentes a una conjunción de cláusulas de doble cuerno;
6. Todas las relaciones son equivalentes a una conjunción de fórmulas afines. ^{[ 2 ]}

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 divulgativo. ^{[ 3 ] [ 4 ]} En términos modernos, el problema SAT( S ) se considera un problema de satisfacción de restricciones sobre el dominio booleano . En este ámbito, es habitual 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 en el álgebra universal es el de polimorfismo. Una operación${\displaystyle f:D^{m}\to D}$es un polimorfismo de una relación${\displaystyle R\subseteq D^{k}}$si, para cualquier elección de m tuplas${\displaystyle (t_{11},\dotsc ,t_{1k}),\dotsc ,(t_{m1},\dotsc ,t_{mk})}$de R , sostiene que la tupla obtenida a partir de estas m tuplas aplicando f coordenada por coordenada, es decir${\displaystyle (f(t_{11},\dotsc ,t_{m1}),\dotsc ,f(t_{1k},\dotsc ,t_{mk}))}$, está en R. Es decir, una operación f es un polimorfismo de R si R es cerrado bajo f : al aplicar f a cualquier tupla en R se obtiene otra tupla dentro de R. Se dice que un conjunto de relaciones Γ tiene un polimorfismo f si toda 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 finito sobre el dominio booleano. El problema CSP(Γ) es decidible en tiempo polinomial si Γ tiene una de las siguientes seis operaciones como polimorfismo:

1. la operación unaria constante 1;
2. la operación unaria constante 0;
3. la operación AND binaria ∧;
4. la operación OR binaria ∨;
5. la operación de mayoría ternaria${\displaystyle \operatorname {Mayoría} (x,y,z)=(x\wedge y)\vee (x\wedge z)\vee (y\wedge z);}$
6. la operación minoritaria ternaria${\displaystyle \operatorname {Minoría} (x,y,z)=x\oplus y\oplus z.}$

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 denomina primitiva positiva definible , o abreviada pp-definible , de un conjunto Γ de relaciones si R ( v ₁ , ... , v _k ) ⇔ ∃ x ₁ ... x _m . C se cumple para alguna conjunción C de restricciones de Γ y ecuaciones sobre las variables { v ₁ ,..., v _k , x ₁ ,..., 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-definida 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 desde Γ 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 Γ. Recíprocamente, 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 antitona . 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 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 ajustó posteriormente: CSP(Γ) es resoluble 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 la dicotomía de Schaefer también se ha generalizado para utilizar la lógica proposicional de grafos en lugar de la lógica booleana. ^{[ 9 ]}

Si el problema consiste en contar el número de soluciones, que se denota por #CSP(Γ), entonces existe un resultado similar para el dominio binario por 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 más grandes, Bulatov y Dalmau dieron una condición necesaria para la satisfacibilidad en tiempo polinomial. ^{[ 11 ]} Sea Γ un lenguaje de restricciones 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${\displaystyle m(x,y,y)=m(y,y,x)=x.}$Un ejemplo de una operación de Mal'tsev es la operación 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 Minoría como un 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${\displaystyle m(V,F,V)}$y${\displaystyle m(F,T,F)}$. Un ejemplo de uno menos simétrico viene dado por${\displaystyle m(x,y,z)=(x\wedge z)\vee (\neg y\wedge (x\vee z))}$En otros dominios, como los grupos , algunos ejemplos de operaciones de Mal'tsev incluyen:${\displaystyle x-y+z}$y${\displaystyle xy^{-1}z.}$ 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 tratabilidad de #CSP(Γ). Sin embargo, la ausencia de un polimorfismo de Mal'tsev para Γ implica la #P-dureza de #CSP(Γ).

• Teoremas de clasificación Max/min CSP/Ones , un conjunto similar de restricciones para problemas de optimización.