Teorema de Cook-Levin - Cook–Levin theorem

Na teoria da complexidade computacional , o teorema de Cook-Levin , também conhecido como teorema de Cook , afirma que o problema de satisfatibilidade booleano é NP-completo . Ou seja, está em NP , e qualquer problema em NP pode ser reduzido em tempo polinomial por uma máquina de Turing determinística ao problema de satisfatibilidade booleana.

O teorema é nomeado após Stephen Cook e Leonid Levin .

Uma conseqüência importante desse teorema é que se existe um algoritmo de tempo polinomial determinístico para resolver a satisfatibilidade booleana, então todo problema NP pode ser resolvido por um algoritmo de tempo polinomial determinístico. A questão de saber se tal algoritmo para satisfatibilidade booleana existe é, portanto, equivalente ao problema P versus NP , que é amplamente considerado o problema não resolvido mais importante na ciência da computação teórica.

Contribuições

O conceito de NP-completude foi desenvolvido no final dos anos 1960 e no início dos anos 1970 em paralelo por pesquisadores na América do Norte e na URSS . Em 1971, Stephen Cook publicou seu artigo "A complexidade dos procedimentos de prova de teoremas" em anais de conferências do recém-fundado ACM Symposium on Theory of Computing . O artigo subsequente de Richard Karp , "Redutibilidade entre problemas combinatórios", gerou um interesse renovado no artigo de Cook ao fornecer uma lista de 21 problemas NP-completos . Cook e Karp receberam um Prêmio Turing por este trabalho.

O interesse teórico em NP-completude também foi aprimorado pelo trabalho de Theodore P. Baker, John Gill e Robert Solovay que mostraram, em 1975, que resolver problemas NP em modelos de máquina Oracle requer tempo exponencial. Ou seja, existe um oráculo A tal que, para todos os deterministas classes de complexidade de tempo subexponencial T, a classe de complexidade relativizada NP ^A não é um subconjunto de T ^A . Em particular, para este Oracle, P ^Um ≠ NP ^Uma .

Na URSS, um resultado equivalente ao de Baker, Gill e Solovay foi publicado em 1969 por M. Dekhtiar. Posteriormente, o artigo de Leonid Levin , "Problemas de busca universal", foi publicado em 1973, embora tenha sido mencionado em palestras e submetido para publicação alguns anos antes.

A abordagem de Levin era ligeiramente diferente das de Cook e Karp, pois ele considerava os problemas de busca , que exigem encontrar soluções em vez de simplesmente determinar a existência. Ele forneceu 6 desses problemas de pesquisa NP-completos, ou problemas universais . Além disso, ele encontrou para cada um desses problemas um algoritmo que o resolve em tempo ótimo (em particular, esses algoritmos são executados em tempo polinomial se e somente se P = NP ).

Definições

Um problema de decisão está em NP se puder ser resolvido por um algoritmo não determinístico em tempo polinomial .

Uma instância do problema de satisfatibilidade booleana é uma expressão booleana que combina variáveis booleanas usando operadores booleanos .

Uma expressão é satisfatória se houver alguma atribuição de valores verdade às variáveis que torna toda a expressão verdadeira.

Ideia

Dado qualquer problema de decisão em NP, construa uma máquina não determinística que o resolva em tempo polinomial. Então, para cada entrada para aquela máquina, construa uma expressão booleana que calcula se aquela entrada específica é passada para a máquina, se a máquina funciona corretamente e se a máquina para e responde "sim". Então a expressão pode ser satisfeita se e somente se houver uma maneira de a máquina funcionar corretamente e responder "sim", então a satisfatibilidade da expressão construída é equivalente a perguntar se a máquina responderá ou não "sim".

Prova

Esquematizado aceitar computação pela máquina M .

Esta prova é baseada na fornecida por Garey e Johnson.

Existem duas partes para provar que o problema de satisfatibilidade booleana (SAT) é NP-completo. Uma é mostrar que o SAT é um problema NP. A outra é mostrar que todo problema NP pode ser reduzido a uma instância de um problema SAT por uma redução muitos-um em tempo polinomial .

SAT está em NP porque qualquer atribuição de valores booleanos a variáveis booleanas que supostamente satisfaça a expressão dada pode ser verificada em tempo polinomial por uma máquina de Turing determinística. (As declarações verificáveis em tempo polinomial por uma máquina de Turing determinística e solucionáveis em tempo polinomial por uma máquina de Turing não determinística são totalmente equivalentes, e a prova pode ser encontrada em muitos livros didáticos, por exemplo, Introdução de Sipser à Teoria da Computação , seção 7.3 ., bem como no artigo da Wikipedia sobre NP ).

Agora suponha que um determinado problema em NP possa ser resolvido pela máquina de Turing não determinística $M = (Q, Σ, s, F, δ)$ , onde Q é o conjunto de estados, Σ é o alfabeto dos símbolos de fita, $s \in Q$ é o estado inicial, $F \subseteq Q$ é o conjunto de estados de aceitação, e $δ ⊆ (( Q \ F ) × Σ) × ( Q × Σ × {−1, +1})$ é a relação de transição. Suponha ainda que M aceite ou rejeite uma instância do problema no tempo p ( n ) onde n é o tamanho da instância e p é uma função polinomial.

Para cada entrada, I , especificamos uma expressão booleana que é satisfeita se e somente se a máquina M aceita I .

A expressão booleana usa as variáveis definidas na tabela a seguir. Aqui, $q \in Q, - p (n) \leq i \leq p (n), j \in Σ$ e $0 \leq k \leq p (n)$ .

Variáveis	Interpretação pretendida	Quantos?
T _{i, j, k}	Verdadeiro se a célula da fita i contiver o símbolo j na etapa k do cálculo.	O ( p ( n ) ² )
Oi _{, k}	Verdadeiro se o M ' cabeça de leitura / gravação s é a célula de fita i no passo k da computação.	O ( p ( n ) ² )
Q _{q, k}	Verdadeiro se M estiver no estado q na etapa k do cálculo.	O ( p ( n ))

Defina a expressão booleana B como a conjunção das subexpressões na tabela a seguir, para todos $- p (n) \leq i \leq p (n)$ e $0 \leq k \leq p (n)$ :

Expressão	Condições	Interpretação	Quantos?
$T_{i,j,0}$	A célula da fita i inicialmente contém o símbolo j	Conteúdo inicial da fita. Para i > n -1 ei <0, fora da entrada real , o símbolo inicial é o símbolo especial padrão / em branco. $I$	O ( p ( n ))
$Q_{s,0}$		Estado inicial de M .	1
$H_{0,0}$		Posição inicial da cabeça de leitura / gravação.	1
$\neg T_{i,j,k}\lor \neg T_{i,j',k}$	j ≠ j ′	No máximo um símbolo por célula da fita.	O ( p ( n ) ² )
$\bigvee _{j\in \Sigma }T_{i,j,k}$		Pelo menos um símbolo por célula da fita.	O ( p ( n ) ² )
$T_{i,j,k}\land T_{i,j',k+1}\rightarrow H_{i,k}$	j ≠ j ′	A fita permanece inalterada, a menos que seja gravada.	O ( p ( n ) ² )
¬ Q _{q, k} ∨ ¬ Q _{q ′, k}	q ≠ q ′	Apenas um estado de cada vez.	O ( p ( n ))
¬ H _{i, k} ∨ ¬ H _{i ′, k}	eu ≠ eu ′	Apenas uma posição da cabeça por vez.	O ( p ( n ) ³ )
${\begin{array}{l}(H_{i,k}\land Q_{q,k}\land T_{i,\sigma ,k})\to \\\bigvee _{((q,\sigma ),(q',\sigma ',d))\in \delta }(H_{i+d,\ k+1}\land Q_{q',\ k+1}\land T_{i,\ \sigma ',\ k+1})\end{array}}$	k < p ( n )	Transições possíveis na etapa de cálculo k quando a cabeça está na posição i .	O ( p ( n ) ² )
$\bigvee _{0\leq k\leq p(n)}\bigvee _{f\in F}Q_{f,k}$		Deve terminar em um estado de aceitação, o mais tardar na etapa p ( n ).	1

Se houver um cálculo de aceitação para M na entrada I , então B é satisfatório atribuindo T _{i, j, k} , H _{i, k} e Q _{i, k} suas interpretações pretendidas. Por outro lado, se B é satisfazível, então há um cálculo de aceitação para M na entrada I que segue as etapas indicadas pelas atribuições às variáveis.

Existem O ( p ( n ) ² ) variáveis booleanas, cada uma codificável no espaço $O (log p (n))$ . O número de cláusulas é O ( p ( n ) ³ ), então o tamanho de B é O (log ( p ( n )) p ( n ) ³ ). Portanto, a transformação é certamente uma redução muitos-um em tempo polinomial, conforme necessário.

Complexidade

Enquanto o método acima codifica uma máquina de Turing não determinística em complexidade , a literatura descreve abordagens mais sofisticadas em complexidade . O resultado quase linear apareceu pela primeira vez sete anos após a publicação original de Cook. $O(log(p(n))p(n)^{3})$ $O(p(n)log(p(n)))$

Versões generalizadas de satisfatibilidade booleana têm codificações com limites ainda mais fortes: fórmulas booleanas quantificadas (QBF's) codificam máquinas de Turing não determinísticas em complexidade polinomial para o limite de espaço da máquina (em oposição ao limite de tempo), e fórmulas booleanas quantificadas de dependência (DQBF's) codificam não -máquinas de Turing determinísticas em uma complexidade logarítmica ideal para o limite de espaço da máquina.

Consequências

A prova mostra que qualquer problema em NP pode ser reduzido em tempo polinomial (de fato, espaço logarítmico é suficiente) a uma instância do problema de satisfatibilidade booleana. Isso significa que se o problema de satisfatibilidade booleana pudesse ser resolvido em tempo polinomial por uma máquina de Turing determinística , então todos os problemas em NP poderiam ser resolvidos em tempo polinomial e, portanto, a classe de complexidade NP seria igual à classe de complexidade P.

O significado de NP-completude ficou claro pela publicação em 1972 do artigo de referência de Richard Karp , "Reducibility between combinatorial problems", no qual ele mostrou que 21 problemas combinatórios e teóricos de grafos diversos , cada um infame por sua intratabilidade, são NP -completo.

Karp mostrou que cada um de seus problemas era NP-completo reduzindo outro problema (já mostrado como NP-completo) a esse problema. Por exemplo, ele mostrou que o problema 3SAT (o problema de satisfatibilidade booleana para expressões na forma normal conjuntiva com exatamente três variáveis ou negações de variáveis por cláusula) é NP-completo, mostrando como reduzir (em tempo polinomial) qualquer instância de SAT para uma instância equivalente de 3SAT. (Primeiro você modifica a prova do teorema de Cook-Levin, de modo que a fórmula resultante esteja na forma normal conjuntiva, então você introduz novas variáveis para dividir cláusulas com mais de 3 átomos. Por exemplo, a cláusula (A ∨ B ∨ C ∨ D) pode ser substituído pela conjunção de cláusulas (A ∨ B ∨ Z) ∧ (¬Z ∨ C ∨ D), onde Z é uma nova variável que não será usada em nenhum outro lugar da expressão. pode ser preenchido; por exemplo, A pode ser substituído por (A ∨ A ∨ A) e (A ∨ B) pode ser substituído por (A ∨ B ∨ B)).

Garey e Johnson apresentaram mais de 300 problemas NP-completos em seu livro Computers and Intratability: A Guide to the Theory of NP-Completeness , e novos problemas ainda estão sendo descobertos dentro dessa classe de complexidade.

Embora muitas instâncias práticas de SAT possam ser resolvidas por métodos heurísticos , a questão de saber se existe um algoritmo de tempo polinomial determinístico para SAT (e, consequentemente, todos os outros problemas NP-completos) ainda é um famoso problema não resolvido, apesar de décadas de intenso esforço por teóricos da complexidade, lógicos matemáticos e outros. Para obter mais detalhes, consulte o artigo P versus problema NP .

Languages

In other projects