Classe de Problema NP
Por: JPAV • 3/4/2019 • Trabalho acadêmico • 339 Palavras (2 Páginas) • 289 Visualizações
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.
...