Teorema da dicotomia de Schaefer

Teorema da dicotomia de Schaefer Na teoria da complexidade computacional, um ramo da informática, O teorema da dicotomia de Schaefer afirma condições necessárias e suficientes sob as quais um conjunto finito S de relações sobre o domínio booleano produz problemas de tempo polinomial ou NP-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 está em P ou NP-completo, em oposição a uma das classes de complexidade intermediária que se sabe existir. (assumindo P ≠ NP) pelo teorema de Ladner.

Casos especiais do teorema da dicotomia de Schaefer incluem a NP-completude do SAT (o problema de satisfatibilidade booleana) e suas duas variantes populares 1-em-3 SAT e 3SAT não-todos iguais (frequentemente denotado por NAE-3SAT). Na verdade, para essas duas variantes do 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-completos.

Conteúdo 1 Apresentação original 2 Apresentação moderna 3 Propriedades dos Polimorfismos 4 Generalizações 5 Trabalho relatado 6 Veja também 7 References Original presentation Schaefer defines a decision problem that he calls the Generalized Satisfiability problem for S (indicado por SAT(S)), Onde {estilo de exibição S={R_{1},ldots ,R_{m}}} é um conjunto finito de relações sobre variáveis ​​proposicionais. Uma instância do problema é uma fórmula S, ou seja. uma conjunção de restrições da forma {estilo de exibição R_{j}(x_{eu_{1}},ldots ,x_{eu_{n}})} Onde {estilo de exibição R_{j}em S} e a {estilo de exibição x_{eu_{j}}} são variáveis ​​proposicionais. O problema é determinar se a fórmula dada é satisfatível, em outras palavras, se as variáveis ​​podem receber valores tais que satisfaçam todas as restrições dadas pelas relações de S.

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-completo. Um conjunto finito de relações S sobre o domínio booleano define um problema de satisfatibilidade computável em tempo polinomial se qualquer uma das seguintes condições for válida: 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áusulas 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 cláusulas dual-Horn; todas as relações são equivalentes a uma conjunção de fórmulas afins. [2] Por outro lado, o problema SAT(S) é NP-completo.

Modern presentation A modern, apresentação simplificada do teorema de Schaefer é dada em um artigo expositivo por Hubie Chen.[3][4] Em termos modernos, o problema SAT(S) é visto como um problema de satisfação de restrições sobre o domínio booleano. Nesta área, é padrão denotar o conjunto de relações por Γ e o problema de decisão definido por Γ como CSP(C).

Esta compreensão moderna usa a álgebra, em particular, álgebra universal. Para o teorema da dicotomia de Schaefer, o conceito mais importante em álgebra universal é o de um polimorfismo. Uma operação {estilo de exibição f:D^{m}para D} é um polimorfismo de uma relação {estilo de exibição Rsubseteq D^{k}} E se, para qualquer escolha de m tuplas {estilo de exibição (t_{11},dotsc ,t_{1k}),dotsc ,(t_{m1},dotsc ,t_{mk})} de R, sustenta que a tupla obtida dessas m tuplas aplicando f coordenadamente, ou seja. {estilo de exibição (f(t_{11},dotsc ,t_{m1}),dotsc ,f(t_{1k},dotsc ,t_{mk}))} , está em R. Aquilo é, uma operação f é um polimorfismo de R se R é fechado sob f: aplicar f a qualquer tupla em R produz outra tupla dentro de R. Diz-se que um conjunto de relações Γ tem um polimorfismo f se toda relação em Γ tem f como um polimorfismo. Esta definição permite a formulação algébrica do teorema da dicotomia de Schaefer.

Seja Γ uma linguagem de restrição finita sobre o domínio booleano. O problema CSP(C) é decidível em tempo polinomial se Γ tem uma das seis seguintes operações como um polimorfismo: a operação unária constante 0; a operação unária constante 1; a operação E binária ∧; a operação OR binário ∨; a operação de maioria ternária {nome do operador de estilo de exibição {Maioria} (x,y,z)=(xcunha y)v (xcunha z)v (ywedge z);} a operação minoritária ternária {nome do operador de estilo de exibição {Minoria} (x,y,z)=xo mais yo mais z.} Por outro lado, o problema CSP(C) é NP-completo.

Nesta formulação, é fácil verificar se alguma das condições de tratabilidade se mantém.

Properties of Polymorphisms Given a set Γ of relations, há uma conexão surpreendentemente próxima entre seus polimorfismos e a complexidade computacional do CSP(C).

Uma relação R é chamada primitiva positiva definível, ou curto pp-definível, de um conjunto Γ de relações se R(v1, ... , vk) ⇔ ∃x1 ... xm. C vale para alguma conjunção C de restrições de Γ e equações sobre as variáveis {v1,...,vk, x1,..., xm}. Por exemplo, se Γ consiste na relação ternária nae(x,y,z) segurando se x,y,z não são todos iguais, e R(x,y,z) é x∨y∨z, então R pode ser pp-definido por R(x,y,z) ⇔ ∃a. não(0,x,uma) ∧ não(y,z,¬a); esta redução foi usada para provar que o NAE-3SAT é NP-completo. O conjunto de todas as relações que são pp-definíveis de Γ é denotado por ≪Γ≫. Se Γ' ⊆ ≪Γ≫ para alguma restrição finita define Γ e Γ', então CSP(C') reduz para CSP(C).[5] Dado um conjunto Γ de relações, Pol(C) denota o conjunto de polimorfismos de Γ. Por outro lado, se O é um conjunto de operações, então Inv(O) denota o conjunto de relações tendo todas as operações em O como um polimorfismo. Pol e Inv juntos constroem uma conexão Galois. Para qualquer conjunto finito Γ de relações sobre um domínio finito, ≪Γ≫ = Inv(Pol(C)) detém, isso é, o conjunto de relações pp-definíveis de Γ pode ser derivado dos polimorfismos de Γ.[6] Além disso, se Pol(C) ⊆ Pol(C') para dois conjuntos de relações finitas Γ e Γ', então Γ' ⊆ ≪Γ≫ e CSP(C') reduz para CSP(C). Como consequência, dois conjuntos de relações com os mesmos polimorfismos levam à mesma complexidade computacional.[7] Generalizations The analysis was later fine-tuned: CSP(C) é 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 é válido.[8] O teorema da dicotomia de Schaefer foi recentemente generalizado para uma classe maior de relações.[9] Related work If the problem is to count the number of solutions, que é indicado por #CSP(C), então, um resultado semelhante de Creignou e Hermann é válido.[10] Seja Γ uma linguagem de restrição finita sobre o domínio booleano. O problema #CSP(C) é computável em tempo polinomial se Γ tem uma operação de Mal'tsev como um polimorfismo. Por outro lado, o problema #CSP(C) é #P-completo. Uma operação de Mal'tsev m é uma operação ternária que satisfaz {estilo de exibição m(x,y,y)=m(y,y,x)= x.} Um exemplo de uma operação Mal'tsev é a operação Minoritária apresentada no moderno, formulação algébrica do teorema da dicotomia de Schaefer acima. Desta forma, quando Γ tem a operação Minoritária como um polimorfismo, não só é possível decidir CSP(C) em tempo polinomial, mas para calcular #CSP(C) em tempo polinomial. Há um total de 4 Operações Mal'tsev em variáveis ​​booleanas, determinado pelos valores de {estilo de exibição m(T,F,T)} e {estilo de exibição m(F,T,F)} . Um exemplo de menos simétrica é dado por {estilo de exibição m(x,y,z)=(xcunha z)v (neg ywedge (xvee z))} . Em outros domínios, como grupos, exemplos de operações de Mal'tsev incluem {estilo de exibição x-y+z} e {estilo de exibição xy^{-1}z.} Para domínios maiores, mesmo para um domínio de tamanho três, a existência de um polimorfismo de Mal'tsev para Γ não é mais uma condição suficiente para a tratabilidade de #CSP(C). No entanto, a ausência de um polimorfismo de Mal'tsev para Γ ainda implica a #P-dureza de #CSP(C).

Veja também teoremas de classificação Max/min CSP/Ones, um conjunto semelhante de restrições para problemas de otimização Referências ^ Schaefer, Thomas J. (1978). "A Complexidade dos Problemas de Satisfação". ESTOQUE 1978. pp. 216-226. doi:10.1145/800133.804350. ^ Schaefer (1978, p.218 esquerda) define uma fórmula afim como sendo da forma x1 ⊕ ... ⊕ xn = c, onde cada xi é uma variável, c é uma constante, ou seja. verdadeiro ou falso, e "⊕" denota XOR, ou seja. adição em um anel booleano. ^ Chen, Hubie (dezembro 2009). "Um encontro de lógica, Complexidade, e Álgebra". Pesquisas de Computação ACM. 42 (1): 1-32. arXiv:cs/0611018. doi:10.1145/1592451.1592453. ^ Chen, Hubie (dezembro 2006). "Um encontro de lógica, Complexidade, e Álgebra". Notícias SIGACT (Coluna lógica). arXiv:cs/0611018. ^ Chen (2006), p.8, Proposição 3.9; Chen usa redução muitos-um em tempo polinomial ^ Chen (2006), p.9, Teorema 3.13 ^ Chen (2006), p.11, Teorema 3.15 ^ Allender, Eric; terreno para construção, Michael; Immerman, Neil; Schnoor, Henning; Vollmer, Heriberto (Junho 2009). "A complexidade dos problemas de satisfatibilidade: Refinando o teorema de Schaefer" (PDF). Revista de Ciências da Computação e Sistemas. 75 (4): 245-254. doi:10.1016/j.jcss.2008.11.001. Recuperado 2013-09-19. ^ Bodirsky, Manoel; Pentecostes, Michael (2015). "Teorema de Schaefer para Grafos". J. ACM. 62 (3): 19:1-19:52. arXiv:1011.2894. doi:10.1145/2764899. ^ Creignou, Nádia; Hermann, Miki (1996). "Complexidade de problemas de contagem de satisfatibilidade generalizada". Informação e Computação. 125 (1): 1-12. doi:10.1006/inco.1996.0016. ISSN 0890-5401. Categorias: Programação de restriçõesTeoremas na teoria da complexidade computacional