Teorema da dicotomia de Schaefer

Em teoria da complexidade computacional, um ramo da ciência da computação, o Teorema da dicotomia de Schaefer declara condições necessárias e suficientes sob as quais um conjunto finito S de relações sobre o domínio Booleano gera problemas de tempo polinomial ou problemas NP-completos quando as relações de S são usadas para restringir algumas das variáveis proposicionais. É chamado teorema da dicotomia porque a complexidade do problema definido por S ou está em P ou NP-complete, ao contrário das classes de complexidade intermediária que sabemos que existem (assumindo P ≠ NP) de acordo com o teorema de Ladner.

Casos especiais do teorema da dicotomia de Schaefer incluem a NP-completude de SAT (o Problema de satisfatibilidade booleana) e suas duas variantes populares SAT 1-em-3 e 3SAT Nem-Todos-Iguais (comumente chamado 3SAT-NTI). De fato, para essas duas variantes de SAT, o teorema da dicotomia de Schaefer mostra que suas versões monótonas(onde negações de variáveis não são permitidas) também são NP-completas.

Apresentação original

Schaefer define um problema de decisão que ele chama de problema da Satisfatibilidade Generalizado para S (SAT(S)). Uma instância do problema é uma fórmuka-S, 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}$ são variáveis proposicionais. O problema é determinar se a dada fórmula é satisfatível, em outras palavras se podemos associar valores às variáveis tais que eles satisfaçam todas as restrições.

Schaefer identifica seis classes de conjuntos de relações booleana para os quais SAT(S) está em P e prova que todos os outros conjuntos de relações geram um problema NP-completo. Um conjunto finito de relações S sobre o domínio booleano define um problema de satisfatibilidade computável de tempo polinomial se alguma das condições que segue for verdadeira:

1. todas as relações que não são constantemente falsas são verdadeiras quando todos os seus argumentos são verdadeiros;
2. todas as relações que não são constantemente falsas são verdadeiras quando todos os seus argumentos são falsos;
3. todas as relações são equivalentes a uma conjunção de cláusuloas binárias;
4. todas as relações são equivalentes a uma conjunção de cláusulas de Horn;
5. todas as relações são equivalentes a uma conjunção de dual-Horn clauses;
6. todas as relações são equivalentes a uma conjunção de de formulas afins (ex: $x_1\oplus \cdots \oplus x_n=\text{true}$).

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

Apresentação moderna

Uma apresentação moderna e ampla do teorema da dicotomia de Schaefer é dada numa carta expositória por Hubie Chen. Em termos modernos, o problema SAT(S) é visto como um problema de satisfatibilidade de restrições sobre o Domínio booleano. Nessa área, é comum se denotar o conjunto de relações por Γ e o problema de decisão definido por Γ como CSP(Γ).

Esse entendimento moderno usa álgebra, em particular [universal algebra]]. Para o teorema da dicotomia de Schaefer, o conceit mais importante da álgebra universal é o de polimorfismo. Uma operação $f:D^m\to D$ é um polimorfismo de uma relação $R\subseteq D^k$ se, para alguma escolha de m tuplas $(t_{11},\dots ,t_{1k}),\dots ,(t_{m1},\dots ,t_{mk})$ from R, é verdade que a tupla obtida à partir dessas m tuplas se aplicando f no sentido das coordenadas, ou seja $(f(t_{11},\dots ,t_{1k}),\dots ,f(t_{m1},\dots ,t_{mk}))$, está em R. Isto é, uma operação f é um polimorfismo de R em R se é fechada sobre f: aplicarf a quaisquer tuplas em R gera outra tupla dentro de R. Um conjunto de relações Γ tem um polimorfismo f se toda relação em Γ, f tem um polimorfismo. Essa definição nos permite formular algebricamente o teorema da dicotomia de Schaefer.

Seja Γ uma linguagem de restrições finita sobre o domínio Booleano. O problema em CSP(Γ) é decidível em tempo polinomial se Γ tem alguma das seis operações como um polimorfismo:

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

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

Nessa formulação, é fácil perceber se alguma das condições de In this formulation, it is easy to check if any of the tratabilidade é verdadeira.

Generalizações

A análise foi mais tarde aperfeiçoada: CSP(Γ) ou é solúvel em co-NLOGTIME, L-completo, NL-completo, ⊕L-completo, P-completo ou NP-completo e dado Γ, pode-se decidir em tempo polinomial qual desses casos acontece.

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

Material relacionado

Se o problema é contar o número de soluções, o qual é denotado por #CSP(Γ), então um resultado similar por Bulatov e Dalmau serve.

Seja Γ uma linguagem de restrições finita sobre o domínio domínio Booleano. O problema #CSP(Γ) é computável em tempo polinomial se Γ tem uma operação de Mal'tsev como um polimorfismo. Caso contrário, o problema #CSP(Γ) é #P-completo.

Uma operação de Mal'tsev m é uma operação ternária que satisfaz $m(x,y,y)=m(y,y,x)=x.$ Um exemplo de operação de Mal'tsev é a operação de Minoria dada na formulação moderna, algébrica do Teorema da dicotomia de Schaefer acima. Portanto, quando Γ tem a operação de Minoria como um polimorfismo, não é somente possível decidir CSP(Γ) em tempo polinomial, como também computar #CSP(Γ) em tempo polinomial. Outros exemplos de operações de Mal'tsev incluem $x-y+z$ e $x{y}^{-1}z.$

Para domínios maiores, mesmo um domínio de tamanho três, a existência do polimorfismo de Mal'tsev polymorphism para Γ não é mais uma condição suficiente para a tratabilidade de #CSP(Γ). Entretando, a ausência do polimorfismo de Mal'tsev para Γ ainda implica na #P-dificuldade de #CSP(Γ).