Completude fraca e forte

O que um algoritmo pseudo-polinomial nos diz sobre o problema que resolve? Não vejo como o tempo de execução melhora se o algoritmo for exponencial no comprimento da entrada e polinomial no valor da entrada; Então, como explicar essa mudança de exponencial para polinomial?

Como afirmado em " Computadores e Intratabilidade: um Guia para a Teoria da Completude NP " Um algoritmo de tempo pseudo-polinomial exibirá ' comportamento exponencial ' somente quando confrontado com instâncias que contêm números ' exponencialmente grandes ', o que pode ser raro para as aplicações em que estamos interessados. Nesse caso, esse tipo de algoritmo pode servir a nossos propósitos quase tão bem quanto um algoritmo de tempo polinomial. ”

Você pode considerar a mochila como um bom exemplo de problema de Np completo fraco . Nesse caso, a complexidade da solução de programação dinâmica é$O(nW)$o que é bom na maioria dos casos práticos .

Sabe-se que não há algoritmo de tempo pseudo-polinomial para problemas de Strong NP-Complete (como Steiner Tree ), a menos que P = NP.

Esta resposta refere-se a algoritmos quase- polinomiais, e não a algoritmos pseudopolinomiais .

Um algoritmo quasipolinomial nos diz que o problema provavelmente não é difícil para o NP. A (certa) Hipótese de Tempo Exponencial (ETH) comumente conhecida afirma que a 3SAT$n$ variáveis ​​requer tempo $2^{\Omega(n)}$. Como o 3SAT está no NP, o ETH implica que qualquer problema de NP completo requer tempo$2^{n^{\Omega(1)}}$, que cresce mais rápido do que o quase-polinomial (supondo que o último seja $2^{\log^{O(1)} n}$)