Please enable JavaScript.
Coggle requires JavaScript to display documents.
P, NP e NP - Complete, 604D4468-BDC9-4506-997B-6DDF0839B810, 5F00A1DD-1927…
P, NP e NP - Complete
P - "polynomial" -> problemas que podem ser resolvidos por algoritmos em ordem de tempo polinomial -> problemas de decisão (sim ou não)
-
-
Há alguns problemas de decisão que ainda não possuem resolução por meio de um algoritmo (undecidable, enquanto os que possuem são chamdos de decidable)
Há também problemas cujas resoluções não foram encontradas por meio de um algoritmo polinomial, mas não há prova de ser imposível (Ex: Circuito hamiltoniano, Knapsack, Partition, Graph-coloring, Bin-packing)
Por mais que propor uma solução para um problema de decisão possa ser computacionalmente exigente, checar uma proposta de solução tende a ser computacionalmente fácil
NP - "nondeterministic polynomial" -> problemas de decisão que podem ser resolvidos por algoritmos de polinomios não determinados
A maior parte dos problemas de decisão se encontram nessa classe, inclusive, todos os problemas que podem ser encontrados em P estão em NP
Problemas de tipo P podem admitir solução como se fossem problemas do tipo NP sem o estágio de gerar candidatos a resposta
-
NP - Complete -> problemas que estão na classe NP, sendo todos os problemas em NP polinomialmente redutíveis a esse np - Complete
Para um problema de decisão D1 ser polinomialmente redutível para outro problema de decisão D2, deve haver uma função t que :
-
-
-
Para provar que um problema está em NP - Complete, há dois passos
-
Mostrar que todo problema em NP é redutível para o problema em um tempo polinomial (pode ser provado a partir da redução de um problema já conhecido e provado que está em NP - Complete)
"tractable" - Problemas cuja resolução tenha eficiência de tempo de ordem polinomial; "intractable" - Resolução não possui ordem de grandeza polinomial.
-
-
-
