Saltar para o conteúdo

Teorema da Dicotomia de Schaefer

Origem: Wikipédia, a enciclopédia livre.

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.[1] 

É 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[editar | editar código-fonte]

Schaefer define um problema de decisão chamado de Problema da Satisfatibilidade Generalizada para (denotado por SAT(''S'')). Uma instância do problema é uma S formula, ou seja, uma conjunção de restrições da forma  onde R é uma relação em Sã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. [2]

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

Apresentação Moderna[editar | editar código-fonte]

ma apresentação moderna e linear do teorema de Schaefer é dado em um artigo expositivo por Hubie Chen.[3][4] 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   é polimorfismo de uma relação  se para qualquer escolha de m tuplas de R,  há de que a tupla obtida destas m tuplas pela aplicação de f em coordenação , 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
  6. A operação ternária da minoridade 

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[editar | editar código-fonte]

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(v1, ... , vk) ⇔ ∃x1 ... xm. C possui de alguma conjunção de C de restrições de Γ e equações sobre as variáveis  {v1,...,vk, x1,...,xm}. 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) é xyz, então R pode ser pp-definida por R(x,y,z) ⇔ ∃a. nae(0,x,a) ∧ nae(y,za); 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(Γ).[5]

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. PolInv 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 Γ.[6] 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.[7]

Generalizações[editar | editar código-fonte]

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.[8]

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

Trabalhos Relacionados[editar | editar código-fonte]

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.[10]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  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  and

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(Γ).

Referências[editar | editar código-fonte]

  1. Schaefer, Thomas J. (1978). «The Complexity of Satisfiability Problems». STOC 1978. pp. 216–226. doi:10.1145/800133.804350 
  2. Schaefer (1978, p.218 left) defines an affine formula to be of the form x1 ⊕ ... ⊕ xn = c, where each xi is a variable, c is a constant, i.e. true or false, and "⊕" denotes XOR, i.e. addition in a Boolean ring.
  3. 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 
  4. Chen, Hubie (dezembro de 2006). «A Rendezvous of Logic, Complexity, and Algebra». ACM. SIGACT News (Logic Column) 
  5. Chen (2006), p.8, Proposition 3.9; Chen uses polynomial-time many-one reduction
  6. Chen (2006), p.9, Theorem 3.13
  7. Chen (2006), p.11, Theorem 3.15
  8. Allender, Eric; Bauland, Michael; Immerman, Neil; Schnoor, Henning; Vollmer, Heribert (junho de 2009). «The complexity of satisfiability problems: Refining Schaefer's theorem» (PDF). Elsevier. Journal of Computer and System Sciences. 75 (4): 245–254. doi:10.1016/j.jcss.2008.11.001. Consultado em 19 de setembro de 2013 
  9. Bodirsky, Manuel; Pinsker, Michael (2010). «Schaefer's theorem for graphs». CoRR. abs/1011.2894. 2894 páginas. Bibcode:2010arXiv1011.2894B. arXiv:1011.2894Acessível livremente 
  10. Creignou, Nadia; Hermann, Miki (1996). «Complexity of generalized satisfiability counting problems». Information and Computation. 125 (1): 1-12. ISSN 0890-5401. doi:10.1006/inco.1996.0016