Problemas NP-Completo

Os NP são problemas que ainda não possuem um algoritmo com uma solução eficiente em relação a tempo polinomial.  O que os torna umas das grandes questões ainda em aberto na ciência da computação.

Os problemas NP são o inverso de problemas P, chamados de polinomiais que possuem um tempo de resolução aceitável com os computadores atuais.

Conhecer e saber como os problemas NP-completos funcionam é interessante pois frequentemente eles aparecem no dia-a-dia e tendo esse conhecimento você será capaz de identificá-los e mediar a sua solução com base em uma solução que seja aproximada ao que busca.

Um dos problemas NP mais citados é o caixeiro viajante, onde dado um ponto inicial e diversos pontos para entrega é necessário traçar uma rota encontrando o menor caminho a ser percorrido, a principio parece algo simples, porém conforme crescem os números de pontos de paradas, aumenta a quantidade de opções de maneira muito rápida, onde por exemplo em uma rota com 19 pontos de parada um computador levaria 73 anos para calcular a melhor rota. Muito né? Isto faz com que o computador seja incapaz de apresentar uma resposta satisfatória com um número maior de pontos de parada, caracterizando um problema NP.

Outro fato interessante sobre os problemas NP é que a base de criptografia de chaves públicas atualmente se baseia em um problema NP, então caso algum problema NP fosse resolvido abriria um caminho para quebra de alguns dos padrões de segurança atual.

Os problemas NP estão listados como um dos problemas do milênio e possui um prêmio para quem consiga encontrar uma solução.