P, NP and NP-Complete Problems
Tractable
Untractable
Solvable in O(p(n))
Not solvable in O(p(n))
Computacional complexity
P and NP problems
P problems
NP problems
problema de decisão e se conhece uma maneira de resolvê-lo com custo limitado superior polinomial, algoritmo determinístico (toda vez que roda um programa para uma entrada x, sempre teremos uma saída y)
Problemas não tratáveis são aqueles cujo custo é exponencial ou maior, ou seja, intratáveis, é um problema resolvido de maneira muito, muito lenta. Caso a entrada seja minimamente não trivial, é quase impossível rodar o algoritmo.
O que podemos fazer?
Utilizar estratégias para tal, em um tempo bom, contudo, não há a certeza de que a resposta dada é a melhor possível. O algoritmo em questão pode até mesmo não te dar uma resposta, ainda que exista sim uma resposta. Ou seja, não é confiável. Ele não é exaustivo. Exatidão versus Eficiência!
Problemas não-tratáveis
-TSP - problema do caixeiro viajante
-Coloração de grafos
-Knapsack problem - problema da mochila
problemas de decisão, resolvidos por algoritmos com custo limitados superiormente por polinômio, algoritmo pode ser determinístico. É visível, assim, que P é um subconjunto de NP.
P versus NP é o maior problema da área da ciência da computação. Não há provas concretas ainda que digam com certeza que P = NP ou mesmo que P != NP. Tudo que e feito hoje parte do pressuposto de que P!=NP, logo, se alguém um dia provar o contrário as implicações serão bastante drásticas, o mundo precisaria reescrever muitos dos seus algoritmos e modos de pensar que já estão bastante firmados no imaginário popular.
-Hamiltonian circuit problem
-Partition problem
-Bin-packing problem
-Graph-coloring problem
-Integer linear programming problem
Deterministic vs Non-deterministic
Deterministic
Non-deterministic
NP-Complete Problems
- it belongs to class NP
- every problem in NP is polynomially reducible to D