# 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 ou NP-completo quando as relações de S são usadas para restringir algumas das variáveis proposicionais.
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}},\ldots ,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:
* Todas as relações que não são falsas de forma constante são verdadeiras quando todos os seus argumentos são verdadeiros;
* Todas as relações que não são falsas de forma constante são verdadeiras quando todos os seus argumentos são falsos;
* Todas as relações são equivalentes à conjunção de cláusulas binárias;
* Todas as relações são equivalentes à conjunção de cláusulas de Horn;
* Todas as relações são equivalentes à conjunção de dupla-cláusula de Horn;
* 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},\dotsc ,t_{1k}),\dotsc ,(t_{m1},\dotsc ,t_{mk})$ de R, há de que a tupla obtida destas m tuplas pela aplicação de f em coordenação $(f(t_{11},\dotsc ,t_{m1}),\dotsc ,f(t_{1k},\dotsc ,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:
* A operação unária constante 0;
* A operação unária constante 1;
* A operação AND binária ∧;
* A operação OR binária ∨;
* A operação ternária da maioridade $\operatorname {Majority} (x,y,z)=(x\wedge y)\vee (x\wedge z)\vee (y\wedge z);$
* A operação ternária da minoridade $\operatorname {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$_1$, ... , v$_k$) ⇔ ∃x$_1$ ... x$_m$. C possui de alguma conjunção de C de restrições de Γ e equações sobre as variáveis {v$_1$,...,v$_k$, x$_1$,...,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 $xy^{-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(Γ).