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.
[1]
É 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 onde R é uma relação em S e 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:
- todas as relações que não são constantemente falsas são verdadeiras quando todos os seus argumentos são verdadeiros;
- todas as relações que não são constantemente falsas são verdadeiras quando todos os seus argumentos são falsos;
- todas as relações são equivalentes a uma conjunção de cláusuloas binárias;
- todas as relações são equivalentes a uma conjunção de cláusulas de Horn;
- todas as relações são equivalentes a uma conjunção de dual-Horn clauses;
- todas as relações são equivalentes a uma conjunção de de formulas afins (ex: ).
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.[2] 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 é um polimorfismo de uma relação se, para alguma escolha de m tuplas from R, é verdade que a tupla obtida à partir dessas m tuplas se aplicando f no sentido das coordenadas, ou seja , 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:
- a operação constante unária 0;
- a operação constante unária 1;
- a operação binária AND ∧;
- a operação binária OR ∨;
- a operação ternária de maioria
- a operação ternária de minoria
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.[3]
O teorema da dicotomia de Schaefer foi recentemente generalizado como sendo uma classe maior de relações.[4]
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.[5]
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 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 e
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(Γ).
Referências
- ↑ Schaefer, Thomas J. (1978). «The Complexity of Satisfiability Problems». STOC 1978. pp. 216–226. doi:10.1145/800133.804350
- ↑ Chen, Hubie (dezembro de 2009). «A Rendezvous of Logic, Complexity, and Algebra». ACM. ACM Computing Surveys. 42 (1). 1 páginas. doi:10.1145/1592451.1592453
- ↑ Allender, Eric; Bauland, Michael; Immerman, Neil; Schnoor, Henning; Vollmer, Heribert (junho de 2009). «The complexity of satisfiability problems: Refining Schaefer's theorem». Elsevier. Journal of Computer and System Sciences. 75 (4): 245–254. doi:10.1016/j.jcss.2008.11.001
- ↑ Bodirsky, Manuel; Pinsker, Michael (2010). «Schaefer's theorem for graphs». CoRR. abs/1011.2894. 2894 páginas. Bibcode:2010arXiv1011.2894B. arXiv:1011.2894
- ↑ Bulatov, Andrei; Dalmau, Víctor (2007). «Towards a dichotomy theorem for the counting constraint satisfaction problem». Information and Computation. 205 (5): 651-678. ISSN 0890-5401. doi:10.1016/j.ic.2006.09.005