Teorema de Cook-Levin

Na teoria da complexidade computacional, o teorema de Cook-Levin, também conhecido como teorema de Cook, afirma que o problema de satisfatibilidade booleana é NP-completo. Isto é, qualquer problema em NP pode ser reduzido em tempo polinomial por uma máquina de Turing determinística para o problema de determinar se uma fórmula booleana é satisfatível.

Uma importante consequência desse teorema é que se existe um algoritmo de tempo polinomial para resolver a satisfatibilidade, então existe um algoritmo de tempo polinomial para resolver todos os problemas em NP. Crucialmente, o mesmo acontece para qualquer problema NP-completo.

A questão de se tal algoritmo existe é chamada de o Problema P versus NP e esse é amplamente considerado o mais importante problema sem solução da teoria da computação. O teorema é atribuído a Stephen Cook e Leonid Levin.

Contribuições

O conceito de NP-completude foi desenvolvido do final dos anos 60 ao começo dos anos 70 em paralelo em pesquisas dos Estados Unidos e União Soviética. Nos EUA em 1971, Stephen Cook publicou o documento "The complexity of theorem proving procedures" na conferencia de procedimentos da recém fundada ACM Symposium on Theory of Computing. O documento subsequente de Richard Karp, "Reducibility among combinatorial problems", gerou um novo interesse no documento de Cook gerando a lista dos 21 problemas NP-completos. Cook e Karp receberam um Prêmio Turing por esse trabalho.

Outra importante contribuição de Karp foi o anúncio de que muitos problemas NP-completos, que pareciam intratáveis no pior caso, são geralmente fáceis para a maioria dos casos gerados aleatoriamente. Em 1984, Levin ampliou esse resultado provando que alguns dos problemas NP são completos no caso médio.

O interesse teórico em NP-completude também foi reforçado pelo trabalho de Theodore P. Baker, John Gill, e Robert Solovay que mostrou que resolvendo problemas NP no modelo da máquina oráculo requer um tempo exponencial.

Na União Soviética, um resultado equivalente ao de Baker, Gill, e Solovay foi publicado em 1969 por M. Dekhtiar. Posteriormente, um documento de Levin, "Universal search problems", foi publicado em 1973, embora isso tenha sido mencionado em conversas e submetido a publicação alguns anos antes.

A abordagem de Levin foi um pouco diferente da de Cook e Karp no sentido de que ele considera problemas de busca, que exigem encontrar soluções em vez de apenas determinar que existem. Ele forneceu seis tais problemas NP-completos de busca, ou problemas universais, e adicionalmente descobriu que cada um tem um algoritmo que resolve em tempo ideal.Predefinição:Vague

Definições

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

Um caso do problema booleano da satisfatibilidade é uma expressão booleana que combina variáveis booleanas usando operadores booleanos.

Uma expressão é satisfatível se existe alguma atribuição de valores as variáveis que faz toda a expressão verdadeira.

Ideia

Dado qualquer problema de decisão em NP, construir uma Máquina de Turing não determinística que o resolva em tempo polinomial. Então, para cada entrada nessa máquina, construir uma expressão booleana tal que a entrada é passada para a máquina, a máquina roda corretamente, sempre que a máquina dá a resposta "sim". Então a expressão pode ser satisfeita se e somente se existe um forma da máquina rodar corretamente e a resposta ser "sim", então a satisfatibilidade da expressão construída é equivalente a perguntar se a máquina vai responder "sim".

Prova

Essa prova é baseada na que foi dada por Garey e Johnson.

Existem duas partes para provar que o problema booleano da satisfatibilidade (SAT) é NP-completo. Uma é mostrar que SAT é um problema NP. E a outra é mostrar que cada problema NP pode ser reduzido para um caso de um problema SAT por uma redução em tempo polinomial muitos-para-um.

SAT é NP porque qualquer atribuição de valores booleanos a variáveis booleanas que é necessária para satisfazer 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 um Máquina da Turing Determinística e solú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 vários livros, por exemplo o livro de Sipser: Introdução a Teoria da Computação, capitulo 7.3.).

Agora supondo que o problema dado em NP pode ser resolvido por uma Máquina de Turing não determinística M = (Q, Σ, s, F, δ), onde Q é o conjunto de estados, Σ é o alfabeto de entrada, s ∈ Q é o estado inicial, F ⊆ Q é o conjunto de estados de aceitação, e δ: Q × Σ → Q × Σ × {−1, +1} é o conjunto das transições. Suponha ainda que M aceita ou rejeita uma cadeia de um problema em tempo p(n) onde n é o tamanho da cadeia e p é a função polinomial.

Para cada entrada, I, nos especificamos uma expressão booleana que é satisfatível se e somente se a maquina M aceita I.

A expressão booleana utiliza as variáveis definidas na tabela seguinte. Aqui, q ∈ Q, −p(n) ≤ i ≤ p(n), j ∈ Σ, e 0 ≤ k ≤ p(n).

Variáveis	Interpretação pretendida	Quanto?
Tijk	Verdadeiro se a célula de fita i contém o simbolo j no passo k da computação.	O(p(n)2)
Hik	Verdadeiro se M's a cabeça de escrever/ler esta na célula de fita i no passo k da computação.	O(p(n)2)
Qqk	Verdadeiro se M esta no estado q no passo k da computação.	O(p(n))

Definir a expressão booleana B para ser conjunção de sub-expressões na seguinte tabela, para todo −p(n) ≤ i ≤ p(n) e 0 ≤ k ≤ p(n):

Expressões	Condições	Interpretação	Quanto?
Tij0	Célula da fita i inicialmente contém o simbolo j	Conteúdo inicial da fita. Para i > n-1 e i < 0, fora a entrada real I, o simbolo inicial é o simbolo especial padrão/branco.	O(p(n))
Qs0		Estado inicial de M.	1
H00		Posição inicial da cabeça de ler/escrever.	1
Tijk → ¬ Tij′k	j ≠ j′	Um simbolo para cada célula de fita	O(p(n)2)
Tijk ∧ Tij′(k+1) → Hik	j ≠ j′	Fita permanece inalterada, ao menos escrita.	O(p(n)2)
Qqk → ¬ Qq′k	q ≠ q′	apenas um estado por vez	O(p(n))
Hik → ¬ Hi′k	i ≠ i′	Apenas uma posição de cabeça por vez	O(p(n)2)
(Hik ∧ Qqk ∧ Tiσk) → $\bigvee$(q, σ, q′, σ′, d) ∈ δ(H(i+d)(k+1) ∧ Qq′(k+1) ∧ Tiσ′(k+1))	k<p(n)	Possível transições na computação do passo k quando a cabeça esta na posição i.	O(p(n)2)
$\bigvee$f ∈ F Qfp(n)		Deve terminar em um estado de aceitação	1

Se existe uma computação aceita em M para a entrada I, então B é satisfatível atribuindo T_ijk, H_ik e Q_ik em suas interpretações. Por outro lado, se B é satisfatível, então há um cálculo para aceitar M sobre a entrada I que segue os passos indicados pela atribuição de variáveis.

Existem O(p(n)²) variáveis booleanas, cada codificada) 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)²). Assim, a transformação é certamente uma redução em tempo polinomial, como queríamos.

Consequências

A prova mostra que qualquer problema NP pode ser reduzido em tempo polinomial (de fato, espaço logaritmo suficiente) para uma instância do problema de SAT. Isso significa que se SAT pode ser resolvido em tempo polinomial por uma Máquina de Turing Determinística, então todos os problemas NP podem ser resolvidos em tempo polinomial, e então a complexidade da classe NP seria igual a complexidade da class P.

O significado de NP-completude ficou claro na publicação em 1972 do importante documento de Richard Karp, "Reducibility among combinatorial problems", em que ele mostrou 21 diversos problemas de combinatória e teoria dos grafos, cada um em sua intratabilidade, são NP-completos.

Karp mostrou que cada um dos seus problemas NP-completos, pode ser reduzido para outro problema (já mostrado ser NP-completo) para esse problema. Por exemplo, ele mostrou que o problema 3SAT (para expressões na Forma normal conjuntiva com exatamente três variáveis ou negações por cláusula) é NP-completo mostrando como deduzir (em tempo polinomial) qualquer caso de SAT para um caso equivalente de 3SAT. (Primeiro você modifica a prova do teorema de Cook-Levin, então a formula resultante está na forma normal conjuntiva, então você introduz uma nova variável para dividir cláusulas com mais de 3 átomos. Por exemplo, a cláusula (A ∨ B ∨ C ∨ D) pode ser substituída 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 lugar a não ser na expressão. Cláusulas com menos de 3 átomos podem ser preenchidas; por exemplo, A pode ser substituída por (A ∨ A ∨ A), e (A ∨ B) pode ser substituída por (A ∨ B ∨ B).

Garey e Johnson apresentaram mais de 300 problemas NP-completo em seu livro Computers and Intractability: A Guide to the Theory of NP-Completeness, e novos problemas continuam sendo descobertos como sendo parte dessa classe de complexidade.

Embora muitos casos práticos de SAT possam ser resolvido por métodos heurísticos, a questão de saber se existe a algoritmo determinístico em tempo polinomial para SAT (e consequentemente todos os outros problemas NP-completo) continua um famoso problema insolúvel, apesar de décadas de intenso esforço pelos teóricos da complexidade, lógicos matemáticos, entre outros. Para mais detalhes, veja o artigo Problema de P = NP.