P = NP?

Bem, se fosse uma equação seria fácil responder:

p=np <-> n=1

Mas e se estivermos falando das classes de problemas NP e P?
A classe P envolve problemas que são resolvidos com algoritmos de tempo polinomial (O(n^k) ) enquanto que a classe NP consiste de problemas para os quais não foram encontrados ainda um algoritmo de tempo polinomial….

Um famoso exemplo de um problema da classe NP é o problema do caixeiro viajante, onde um vendedor tem que visitar n cidades, visitando cada cidade exatemente uma vez e terminando na cidade de onde partiu.

Então a pergunta N = NP não poderia ser respondida por enquanto, uma vez que ao mesmo tempo que não determinamos um algoritmo polinomial para os problemas da classe NP, não podemos também garantir que não exista um algoritmo em tempo polinomial que possa resolvê-los…

Essa pergunta só será respondida qdo ou se achar um algoritmo em tempo polinomial para algum problema da classe NP ( e então P será = NP) ou qdo for provado que realmente não existe nenhum algoritmo de tempo polinomial que resolva um problema da classe NP ( e P será diferente de NP)

Anúncios

Deixe um comentário

Preencha os seus dados abaixo ou clique em um ícone para log in:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair / Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair / Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair / Alterar )

Foto do Google+

Você está comentando utilizando sua conta Google+. Sair / Alterar )

Conectando a %s

%d blogueiros gostam disto: