Problema P versus NP

Suponha que você está organizando acomodações habitação para um grupo de quatrocentos alunos universitários. O espaço é limitado e apenas uma centena de estudantes receberão lugares no dormitório. Para complicar, o reitor prestou-lhe uma lista de pares de alunos incompatíveis, e pediu que nenhum par desta lista aparecem na sua escolha final. Este é um exemplo de que os cientistas denominam uma NP-problema, uma vez que é fácil de verificar se uma dada escolha de cem estudantes proposta por um colega de trabalho é satisfatória (isto é, nenhum par a partir da lista o seu colega de trabalho também aparece na lista de Gabinete do Reitor), no entanto, a tarefa de gerar essa lista a partir do zero parece ser tão difícil quanto a ser completamente inviável. Com efeito, o número total de maneiras de escolher cem alunos de quatro centenas de interessados é maior do que o número de átomos no universo conhecido! Assim, nenhuma civilização futuro poderia ter a esperança de construir um supercomputador capaz de resolver o problema pela força bruta, ou seja, verificando todas as combinações possíveis de 100 alunos. No entanto, esta aparente dificuldade só pode refletir a falta de criatividade do seu programador. De fato, um dos problemas pendentes em ciência da computação é determinar se existem perguntas cuja resposta possa ser rapidamente controlados, mas que requerem um tempo muito longo para resolver por qualquer procedimento direto. Problemas como o listado acima, certamente parecem ser deste tipo, mas até agora ninguém conseguiu provar que nenhum deles é realmente tão duro como eles aparecem, ou seja, que não há realmente nenhuma maneira viável para gerar uma resposta com o ajuda de um computador. Stephen Cook e Leonid Levin formulou a P (isto é, fáceis de encontrar) versus PN (ou seja, fácil de verificar) o problema de forma independente em 1971.