Please enable JavaScript.
Coggle requires JavaScript to display documents.
P, NP and NP-Complete Problems - Coggle Diagram
P, NP and NP-Complete Problems
Tractable
Solvable in O(p(n))
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!
-
-
P and NP problems
P 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)
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.
NP problems
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.
-
-
NP-Complete Problems
- every problem in NP is polynomially reducible to D
