suponha que você está organizando acomodações para um grupo de quatrocentos estudantes universitários. O espaço é limitado e apenas cem dos estudantes receberão lugares no dormitório. Para complicar as coisas, O Reitor forneceu-lhe uma lista de pares de alunos incompatíveis, e pediu que nenhum par desta lista aparecesse em sua escolha final., Este é um exemplo do que os cientistas chamam de uma NP-problema, pois é fácil verificar se uma dada escolha de uma centena de alunos propostos por um colega de trabalho é satisfatória (i.é., sem par tomadas a partir do seu colega de trabalho”s lista também aparece na lista do Reitor”s office), no entanto, a tarefa de criação de uma lista a partir do zero parece ser tão difícil como ser completamente impraticável. De fato, o número total de maneiras de escolher cem estudantes dos quatrocentos candidatos é maior do que o número de átomos no universo conhecido!, Assim nenhuma civilização futura poderia alguma vez esperar construir um supercomputador capaz de resolver o problema pela Força bruta; isto é, verificando cada combinação possível de 100 estudantes. No entanto, esta aparente dificuldade pode apenas refletir a falta de Engenho do seu programador. Na verdade, um dos problemas pendentes na ciência da computação é determinar se existem perguntas cuja resposta pode ser rapidamente verificada, mas que exigem um tempo impossivelmente longo para resolver por qualquer procedimento direto., Problemas como a mostrada acima certamente parecem ser deste tipo, mas até agora ninguém conseguiu provar que qualquer deles são realmente tão difícil como aparecem, por exemplo, que realmente não há caminho viável para gerar uma resposta com a ajuda de um computador. Stephen Cook e Leonid Levin formularam o problema P (ou seja, fácil de encontrar) versus NP (ou seja, fácil de verificar) independentemente em 1971.
crédito da imagem: à esquerda, Stephen Cook por Jiří Janíček. CC BY-SA 3, 0