Classe de Problema NP

Projeto e analise de algoritmos – DOCTUM 2018

Classes de problemas NP

• O que é:

Classe de problemas de decisão que podem ser verificados em tempo polinomial.  São formados por problemas que possuem um verificador polinomial para a resposta sim.

• Por que é importante:

Dificilmente você encontrara um problema que não está na classe dos problemas NP que a torna útil para se resolver a grande maioria dos problemas.

 Quando se trata de problemas que se envolve decisões ele e extremamente eficiente, por sempre fazer verificação das saídas.

• Princípios e fundamentos:

Uma máquina que utiliza algoritmos não determinístico tem uma escolha de passos seguintes e faz sempre a escolha ótima, o que é uma característica poderosa porem limitada quando se trata de problemas indecindíveis.

São formados por problemas que possuem um verificador polinomial para a resposta sim. Para qualquer instancia X do problema com resposta Sim, existe um certificado Y, tal que A (X, Y) devolve SIM.

Consome tempo polinomial em X.

---

• Histórico:

Por volta dos anos 60 que a teoria de complexidade, que trata de tais questões, tornou se importante e começou a estruturar a análise de algoritmos, com a formalização da ideia de "algoritmo eficiente". Nessa mesma época surgiram os conceitos de complexidade P e NP e do conceito de NP- completude, que captura de certa maneira a dificuldade de se conseguir algoritmos eficientes para certos problemas. Grosseiramente, um problema em NP é dito NP- completo se qualquer outro problema da classe NP pode ser reduzido eficientemente a ele.

• Exemplos de 3 algoritmos ou problemas.

1-A versão de decisão do problema do caixeiro viajante é da ordem NP. Dado uma matriz de distâncias entre n cidades, o problema é determinar se há uma rota que visita todas as cidades com a distância total menor que k.

2- Fatoração:  Dado um número natural n, encontrar um número natural p, maior que 1 mas menor que n, que seja divisor de n (ou constatar que tal p não existe).

3- Máximo divisor comum:  Encontrar o maior divisor comum de dois números inteiros positivos m e n.

...