I'm wondering if there exists an exact algorithm for some np-complete problem with quasi-polynomial time complexity.

My best guess is 'no', because if there was one (with a reasonable C, not any C), probably to find a way to improve the time complexity to polynomial would be just a matter of time, thus, the P vs. NP question will be already closed.

I researched on internet and seems there is no quasi-polynomial solution for any of the known np-complete problem (I do found pseudo-polynomial algorithms)

So, could somebody point me to some exact quasi-polynomial algorithm for some np-complete problem if such algorithm exists?


  • 9
    $\begingroup$ Wouldn't that violate the Exponential-time hypothesis? I.e. this would imply quasipolynomial-time algorithms for all of NP, which are widely believed not to exist. $\endgroup$
    – Thomas
    Commented Dec 3, 2014 at 4:12
  • $\begingroup$ @Thomas I'm going to take a look to the hypothesis, also I understand if the hypothesis is still alive means there is no quasi-polynomial algorithm then :) for me is a valid answer so feel free to answer this to the question. $\endgroup$ Commented Dec 3, 2014 at 4:16
  • $\begingroup$ This previous question may give useful information: cstheory.stackexchange.com/questions/21571/… $\endgroup$ Commented Dec 14, 2014 at 2:51


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.