2

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?

thanks!

John Flanders
  • 41
  • 3
  • 9
    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. – Thomas Dec 03 '14 at 04:12
  • @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. – John Flanders Dec 03 '14 at 04:16
  • This previous question may give useful information: http://cstheory.stackexchange.com/questions/21571/is-np-in-dtimenpoly-log-n/21660#21660 – Andras Farago Dec 14 '14 at 02:51

0 Answers0