P=NP?

Todo problema não polinomial tem uma resolução polinomial?

Tal desafio é descobrir se os problemas resolvidos por tentativas admitem uma solução rápida. Um computador poderá organizar a grade horária de uma escola em poucos segundos.

Estamos tratando de duas classes, sendo que a principal distinção entre elas está nos problemas que são do tipo  P (tempo polinomial) e aqueles que não são. 

 

Um problema é do tipo P quando ele pode ser resolvido utilizando um algoritmo cujo tempo de execução é limitado por alguma potência fixa do número de símbolos exigidos para especificar os dados iniciais. Caso contrário o problema é chamado não P.

  

Podemos provar que um problema é do tipo P fornecendo um algoritmo que resolva o problema em tempo polinomial. Por exemplo, está na classe P o Problema do Inspetor de Estradas. Em contraste, acredita-se que o Problema do  Caixeiro  Viajante esteja na classe  não P, mas isso nunca foi provado.
 

Coloca-se, então, a seguinte questão:  por que é difícil provar que um dado problema está na classe não P ? A resposta é bastante simples. Você teria que contemplar todos os possíveis algoritmos e mostrar que nenhum deles resolve o problema proposto em tempo polinomial.

Agora a classe NP (nondeterministic polynomial time) é composta pelos problemas para os quais você pode verificar se uma solução proposta é uma solução em tempo polinomial. Claramente temos P⊂NP. Uma conjectura foi então formulada:  P = NP ?  É crença de muitos que a classe NP contenha propriamente a classe P. 

 

 

Referências:

 

STEIN, James D. Como a matemática explica o mundo: o poder dos números no cotidiano. Rio de Janeiro: Elsevier, 2008.