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 Dec 3 '14 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$ – John Flanders Dec 3 '14 at 4:16
  • $\begingroup$ This previous question may give useful information: cstheory.stackexchange.com/questions/21571/… $\endgroup$ – Andras Farago Dec 14 '14 at 2:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.