MatheusMáthica: "O lado interessante e curioso da Matemática"

Sejam Bem-Vindos a MatheusMáthica....

Seguidores

segunda-feira, 3 de maio de 2010

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.

Nenhum comentário:

Postar um comentário