Stephen Cook

Stephen Cook

Biografia

Stephen Arthur Cook , Oont, (nascido 14 de Dezembro de 1939) é um renomado cientista da computação Americano-Canadense e matemático.

Fez grandes contribuições para o campo da teoria da complexidade e da prova da complexidade incluindo a co-descoberta da teoria de NP-completude com Allan Borodin e Leonid Levin.

Cook tornou-se famoso na teoria da computação pelo Teorema de Cook: O problema da satisfabilidade booleana é NP-completo. Por esta descoberta recebeu o Prêmio Turing de 1982.

Cook recebeu seu grau de bacharel em 1961 pela Universidade de Michigan, e fez mestrado e doutorado na Universidade de Harvard, respectivamente em 1962 e 1966. Ele ingressou na Universidade da Califórnia, Berkeley, departamento de matemática em 1966 como Professor assistente, e ficou lá até 1970, quando foi-lhe negado um novo mandato.
Atualmente, é professor de informática da Universidade de Toronto.

Cook é considerado um dos pais da teoria da complexidade computacional. Durante seu doutorado, Cook trabalhou com a complexidade das funções, principalmente sobre a multiplicação.
Em 1971, em sua obra "A Complexidade Do Teorema  da Prova de Procedimentos" , Cook formalizou as noções de redução de tempo polinomial (também conhecido por redução de Cook) e NP-completude, e provou a existência de um problema NP-completo, mostrando que o Problema da Satisfatibilidade Booleana (geralmente conhecida como SAT) é NP-completo.Tal prova ficou conhecida como o Teorema de Cook.

Problema da Satisfatibilidade Booleana

Também conhecido como (SAT), o problema de satisfazibilidade booleana foi o primeiro problema identificado como pertencente à classe de complexidadeNP-completo. O problema consiste em determinar se existe uma determinada valoração para as variáveis de uma determinada fórmula booleana tal que esta valoração satisfaça esta fórmula em questão.

Por exemplo, tomando  x1,x2,x3,x4  como as variáveis boolianas e a expressão ,           (x1 v ¬x3 v x4) /\ (¬x2 v x3 v ¬x4) caso exista uma atribuição de valores para as variáveis da fórmula que torne a fórmula avaliada verdadeira, esta fórmula é considera satisfazível, em contrapartida se nenhuma atribuição levou a uma avaliação da fórmula como verdadeira, ela é considerada insatisfazível.

O Teorema de Cook

Também conhecido como o teorema de Cook-Levin, 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.

 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.

O Resultado Esperado

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 sua resposta for "sim". Então a expressão pode ser satisfeita se e somente se existe uma 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".

...