Teorema da Dicotomia de Schaefer

Em teoria da complexidade computacional, um ramo da Ciência da Computação, o teorema da dicotomia de Schaefer estabelece as condições necessárias e suficientes sob as quais um conjunto finito S de relações sobre o domínio Booleano produza problemas de tempo polinomial ouNP-completo quando as relações de  S são usadas para restringir algumas das variáveis proposicionais. 

É chamado de teorema da dicotomia porque a complexidade do problema definido por S será P ou NP-completo em oposição a alguma das classes de complexidade NP-Intermediário que é sabida existir (assumindo P ≠ NP) pelo teorema de Ladner.

Casos especias do teorema da dicotomia de Schaefer incluem a NP-completude de SAT (o problema da satisfatibilidade Booleana) e suas duas variantes populares 1-in-3 SAT e NAE-3SAT (Not-All-Equal 3SAT). Na verdade, para estas duas variantes de SAT, o teorema da dicotomia de Schaefer nos mostra suas versões monótonas (onde as negações das variáveis não são permitidas) também são NP-completas.

Apresentação Original

Schaefer define um problema de decisão chamado de Problema da Satisfatibilidade Generalizada para S (denotado por SAT(''S'')). Uma instância do problema é uma S formula, ou seja, uma conjunção de restrições da forma $R(x_{i_1},\dots ,x_{i_n})$ onde R é uma relação em S e $x_{i_j}$ão variáveis proposicionais. O problema é determinar se uma dada fórmula formula é satisfatível, ou seja, se as variáveis pode ser valoradas de forma a cumprir todas as restrições.

Schaefer identifica seis classes de conjuntos de relações Booleanas para as quais SAT(S) está em P e prova que todos os outros conjuntos de relações geram um problema NP-complete. Um conjunto finito de relações S sobre o domínio Booleano define um problema de satisfatibilidade computável em tempo polinomial se alguma das condições a seguir se configurar:

1. Todas as relações que não são falsas de forma constante são verdadeiras quando todos os seus argumentos são verdadeiros;
2. Todas as relações que não são falsas de forma constante são verdadeiras quando todos os seus argumentos são falsos;
3. Todas as relações são equivalentes à conjunção de cláusulas binárias;
4. Todas as relações são equivalentes à conjunção de cláusulas de Horn;
5. Todas as relações são equivalentes à conjunção de dupla-cláusula de Horn;
6. Todas as relações são equivalentes à conjunção de fórmulas afim.

Do contrário, o problema SAT(S) é NP-completo.

Apresentação Moderna

ma apresentação moderna e linear do teorema de Schaefer é dado em um artigo expositivo por Hubie Chen. Em termos mais modernos, o problema SAT(S) é visto como um problema da satisfação de restrições sobre o domínio Booleano. Nessa área, por padrão denota-se o conjunto de relações por Γ e o problema de decisão definido po Γ como CSP(Γ).

Este entendimento moderno usa álgebra, em particular, álgebra universal. Para o teorema da dicotomia de Schaefer, o conceito mais importante na álgebra universal é o do polimorfismo. Uma operação  $f:D^m\to D$ é polimorfismo de uma relação $R\subseteq D^k$ se para qualquer escolha de m tuplas$(t_{11},\dots ,t_{1k}),\dots ,(t_{m1},\dots ,t_{mk})$ de R,  há de que a tupla obtida destas m tuplas pela aplicação de f em coordenação $(f(t_{11},\dots ,t_{m1}),\dots ,f(t_{1k},\dots ,t_{mk}))$, está contida R. Isto é, uma operação f é um polimorfismo de R se R é fechado sobre f: aplicar f para quaisquer tuplas em R conterá outra tupla dentro de R. Um conjunto de relações Γ é dito possuir um polimorfismo f se todas as relações dentro de Γ tem f como um polimorfismo. Essa definição permite a formulação algébrica da teoria da dicotomia de Schaefer.

Seja Γ uma linguagem limitada finita sobre o domínio Booleano. O problema CSP(Γ) é decidível em tempo polinomial se Γ possui uma das seis operações a seguir como polimorfismo:

1. A operação unária constante 0;
2. A operação unária constante 1;
3. A operação AND binária ∧;
4. A operação OR binária ∨;
5. A operação ternária da maioridade $\mathrm{Majority}(x,y,z)=(x\wedge y)\vee (x\wedge z)\vee (y\wedge z);$
6. A operação ternária da minoridade $\mathrm{Minority}(x,y,z)=x\oplus y\oplus z.$

Do contrário, o problema CSP(Γ) é NP-completo.

Nesta formulação, é fácil verificar se quaisquer uma das condições de tratamento é garantida.

Propriedades do Polimorfismo

Dado um conjunto Γ de relações, há uma conexão surpreendentemente próxima entre seus polimorfismos e a complexidade computacional de CSP(Γ).

Uma relação R  é chamada de primitiva positiva definível, ou pp-definível, de um conjunto Γ de relações se R(v₁, ... , v_k) ⇔ ∃x₁ ... x_m. C possui de alguma conjunção de C de restrições de Γ e equações sobre as variáveis  {v₁,...,v_k, x₁,...,x_m}. Por exemplo, se Γ consiste da relação ternária nae(x,y,z) tendo que se x,y,z não são iguais, e R(x,y,z) é x∨y∨z, então R pode ser pp-definida por R(x,y,z) ⇔ ∃a. nae(0,x,a) ∧ nae(y,z,¬a); testa mesma redução foi usada para provar que o problema NAE-3SAT é NP-completo. O conjunto de todas as relações que são pp-definíveis de Γ é denotado por ≪Γ≫. Se Γ' ⊆ ≪Γ≫ para quaisquer conjuntos finitos limitados Γ eΓ', então CSP(Γ') é redutível à CSP(Γ).

Dado um conjunto Γ de relações, Pol(Γ) denota o conjunto de polimorfismos de Γ. Se O é um conjunto de operações, então Inv(O) denota o conjunto de relações tendo todas as suas operações em O como polimorfismo. Pol e Inv juntos constroem uma conexão de Galois. Para qualquer conjunto finito Γ de relações sobre um domínio finito, ≪Γ≫ = Inv(Pol(Γ)) contém, isto é, o conjunto de relações pp-definíveis de Γ que podem ser derivadas dos polimorfismos de Γ. Se Pol(Γ) ⊆ Pol(Γ') para dois conjuntos finitos de relações Γ e Γ', então Γ' ⊆ ≪Γ≫ and CSP(Γ') reduzem à CSP(Γ). Por consequência, dois conjuntos de relações possuindo os mesmos polimorfismos levam à mesma complexidade computacional.

Generalizações

A análise foi posteriormente refinada: CSP(Γ) será resolvível em tempo co-NLOG, L-completo, NL-completo, ⊕L-completo, P-completo ou NP-completo e dado Γ, é possível decidir em tempo polinomial qual destes casos é correspondente.

O teorema da dicotomia de Schaefer foi recentemente generalizado para uma classe maior de relações.

Trabalhos Relacionados

Caso o problema seja o de contar o número de soluções, denotado por #CSP(Γ), então um resuldado similar criado por Creignou e Hermann efetiva.Seja Γ uma linguagem finita restringida sobre o domínio Booleano. O problema #CSP(Γ) é computável em tempo polinomial se Γ possuir uma operação Mal'tsev como polimorfismo. Do contrário, o problema #CSP(Γ) é #P-completo. Uma operação Mal'tsev ''m''é uma operação ternária que satisfaz $m(x,y,y)=m(y,y,x)=x.$ Um exemplo de uma operação Mal'tsev é a operação de Minoria dada na formulação moderna do teorema da dicotomia de Schaefer através da álgebra universal na sessão acima. Portanto, quando Γ possuir a operação Minoria como um polimorfismo, é não somente possível decidir CSP(Γ) em tempo polinomial, mas também computar #CSP(Γ) em tempo polinomial. Outros exemplos de operações Mal'tsev incluem $x-y+z$ and $x{y}^{-1}z.$

Para domínios maiores, mesmo para um domínio de tamanho três, a existência de um Maltsev como polimorfismo de Γ não mais é condição suficiente para a tratabilidade de #CSP(Γ). No entanto, a abscência de um polimorfismo Mal'tsev para este Γ ainda implica a #P-dificuldade de #CSP(Γ).