Please enable JavaScript.
Coggle requires JavaScript to display documents.
Problemas P, NP, e NP-Completo - Coggle Diagram
Problemas P, NP, e NP-Completo
Problemas Tratáveis e Intratáveis
Um problema pode ser resolvido em um tempo
polinomial
se o pior caso pertencer a O( p(n) ), onde p(n) é um polinômio que depende de do tamanho da entrada(n)
Se um problema pode ser resolvido em um tempo polinomial, então ele é
Tratável
Caso ele não possa ser resolvido em um tempo polinomial, então ele é
Intratável
Tem esse nome pois seu tempo de execução tem um crescimento exponencial ou fatorial, com instancias um pouco elevadas, o tempo para o algoritmo rodar pode ultrapassar décadas....
Problemas P
(Classe Polinomial)
São problemas que são resolvidos por algoritmo determinista(de decisão) em um tempo polinomial por um algoritmo determinista, ou seja,
tem uma resposta binária como saída
Todo Problema de decisão pode ser resolvido em um tempo polinomial?
Não
Indecidível
Um exemplo desse tipo de Problema foi dado por Alan Turing e é chamado de "problema de parada"
Dado um programa de computador e uma entrada para ele, determine se o programa irá parar com a entrada dada ou continuará trabalhando indefinidamente nela
Nesse caso, o algoritmo não tem como dizer se o programa vai rodar para sempre ou se vai parar, caso ele pare, então é possível afirmar com certeza isso, mas se ele trabalhar eternamente, o algoritmo não pode dizer que o programa não vai parar
Não conhecemos algoritmos que resolvam ele
Decidível
É possível um problema ser decidível e intratável?
Sim
Por exemplo:
Problema do Circuito Hamiltoniano:
Determine para qualquer grafo dado, se ele tem um circuito Hamiltoniano ou não (é um caminho que começa e termina no mesmo vértice e passa por todos os ostros vértices do grafo
É decidível se tiver como escrever um código que resolva esse problema, mesmo se for uma solução ineficiente a ponto de ser intratável (não ter o tempo de execução crescendo de maneira polinomial)
Problemas NP (Classe polinomial não determinística)
É a classe de problemas de decisão que podem ser resolvidos por algoritmos polinomiais não determinísticos
A maioria dos problemas de decisão estão nessa classe, incluindo os da classe P, pois P está contido na classe NP
Isso é verdade pois podemos usar qualquer algoritmo de P na faze de verificação de um algoritmo de NP
A pesar disso o Problema de parada não faz parte da classe NP
Mas não se sabe se NP e P são iguais ou diferentes, como não conseguimos encontrar uma solução P para um problema NP então a gente "considera" que eles não são iguais
Os algoritmos polinomiais não determinísticos são compostos por duas fazes:
Faze não determinística (adivinhação), que gera uma possível resposta correta
Não sabemos como é feita essa adivinhação
Faze determinística (verificação), que verifica se a resposta gerada na etapa anterior é valida
Se essa faze for resolvida de forma polinomial então a esse algoritmo faz parte da classe NP
??Problemas NP-Completos??
Essa classe é um subconjunto de NP em que cada um dos os seus problemas é resultado de uma redução de outro problema de NP
Sendo essa redução feita em tempo polinomial
Se NP!=P
Então NP-Completo está contido em NP e não tem nenhuma intersecção com P(que também é um subConjunto de NP)
Um dos poucos problemas conhecidos que são NP-Completos é o problema de SAT
Quem não está em P nem em NP-Completo é chamado de NP-Intermediário
Se NP==P
Então NP==P==NP-Completo