Universidade Federal de Pernambuco (UFPE)
Centro de Informática (CIn)
Graduação em Ciência da Computação e Engenharia da Computação
IF689 - Informática Teórica
A Questão P vs NP
Suponha que você esteja organizando acomodação para um grupo
de quatrocentos estudantes universitários. O espaço é
limitado e somente cem dos estudantes terão lugar no dormitório.
Para complicar ainda mais, o Pró-reitor lhe deu uma lista de
pares de estudantes incompatíveis, e solicitou que nenhum par dessa
lista apareça na sua escolha final.
Esse é um exemplo do que os cientistas da computação
chamam de problema NP, pois é fácil de verificar se uma dada
escolha de cem estudantes proposta por um colaborador é
satisfatória (i.e., nenhum par tomado da lista desse colaborador
também aparece na lista do Pró-reitor), entretanto a tarefa
de gerar uma lista dessas a partir do nada parece ser tão difícil
quanto completamente impraticável. De fato, o número total de
maneiras de se escolher cem estudantes dos quatrocentos inscritos é
maior que o número de átomos no universo conhecido!
Portanto nenhuma civilização futura poderia sequer ter
esperança de construir um supercomputador capaz de resolver o
problema pela força bruta; ou seja, checando
todas as possíveis combinações de 100 estudantes.
Entretanto, essa dificuldade aparente pode apenas refletir
a falta de engenhosidade de seu programador. Na realidade, um dos problemas
em aberto em ciência da computação é
determinar se existem questões cuja resposta pode ser facilmente
checadas, mas que requerem um tempo impossivelmente longo para resolver
por qualquer procedimento direto.
Problemas como o mencionado acima certamente parecem ser desse tipo, mas
até agora ninguém conseguiu provar que quaisquer deles realmente
são tão difíceis quanto parecem, i.e., que
de fato não existe maneira factível de gerar uma resposta
com a ajuda de um computador. Stephen Cook e
Leonid Levin formularam o problema P (i.e., fácil de achar) versus NP (i.e., fácil de checar)
independentemente em 1971.
Última atualização: 2 de Dezembro de 2005, 10:38hs