Please enable JavaScript.
Coggle requires JavaScript to display documents.
Problemas P, NP e NP-Completos - Coggle Diagram
Problemas P, NP e NP-Completos
Se tratando de complexidade computacional de problemas, como sabemos se um dado algoritmo pode ser executado em tempo polinomial?
DEFINIÇÕES
É dito TRATÁVEL um problema que pode ser resolvido com um algoritmo de complexidade, no pior caso, O(p(n)), onde p(n) é um polinômio para uma entrada de tamanho n.
Como está sendo usada a notação big-Oh, isso implica que problemas resolvíveis em tempo logarítmico (ou em tempo menor) também são resolvíveis em tempo polinomial, e também são tratáveis.
-
Caso contrário, este problema é dito INTRATÁVEL.
-
Formalmente, estes conjuntos P, NP são restritos a problemas de decisão (ex: função booleana)
Algoritmos não-determinísticos: são procedimentos com dois estágios, palpite e verificação
Palpite: Para um input I, o algoritmo gera uma possível solução S
Verificação: Tendo I e S, o algoritmo verifica se S realmente é uma solução
Se a resposta for sim, retorna sim. Caso contrário, o algoritmo pode retornar não, ou continuar tentando
Um algorítmo não-determinístico resolve um problema de decisão se, e somente se, para cada instância com resultado sim do problema, o algoritmo retorna sim em alguma execução
Um algorítmo não-determinístico é dito não-determinístico polinomial se seu estágio de verificação tem eficiência temporal polinomial
-
Problema NP-completo: Atribuição informal para um problema em NP, cuja solução para um input pode ser verificada em tempo polinomial
Problemas NP-completos tem aplicações práticas importantes no cotidiano, e embora geralmente não consigamos escrever algorítmos com uma solução geral ou que resolva todos os casos dado um input, nós conseguimos achar, em tempo polinomial, soluções para uma dada instância específica
Problemas indecidíveis
-
Exemplos
-
-
-
-
O problema da parada, de Turing