Um problema é polinomial se:
Um algoritmo resolve problemas de polinômios
Um algoritmo resolve problemas em um tempo dado por um polinômio
Um algoritmo resolve problemas em um limite de tempo no melhor caso dado por um polinômio
Um algoritmo resolve problemas em um limite de tempo no pior caso dado por um polinômio
O conjunto P é o conjunto de todos os problemas polinomiais possíveis.
Um problema é NP-Completo se for:
NP e P ao mesmo tempo
NP e somente com verificação polinomial(completamente polinomial)
NP-difícil e P ao mesmo tempo
NP-difícil e NP ao mesmo tempo
Qual destas complexidades é polinomial?
2^n
n^2 + n
n^n
n^2 + 3^n
Como se prova que um NP é um NP-Completo:
Redução Polinomial a partir de outro problema conhecido como NP-C.
Por métodos matemáticos avançados.
Redução Polinomial a partir de outro problema conhecido como NP.
Não é possivel provar.
O problema da mochila pertence a qual ou quais tipo(s) de problema?
P
NP
NP-C
BC
O problema da mochila é único e pertence somente aos problemas NP-C.
