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

<p>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.</p>

<p>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)</p>

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

<p>thanks!</p>

CC BY-SA 3.0
2014-12-03T04:12:21.993Z
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 Steinke
CC BY-SA 3.0
2014-12-03T04:16:13.520Z
@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
CC BY-SA 3.0
2014-12-14T02:51:45.657Z
This previous question may give useful information: http://cstheory.stackexchange.com/questions/21571/is-np-in-dtimenpoly-log-n/21660#21660
Andras Farago
<cc.complexity-theory>
Are there NP-complete problems with quasi-polynomial expected time solutions?
John Flanders
# Are there NP-complete problems with quasi-polynomial expected time solutions?

(Asked by: username_0 on 2014-12-03)

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!

**Tags:** cc.complexity-theory

> **Comments:**
> **username_1**: 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.  
> **username_0**: @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.  
> **username_2**: This previous question may give useful information: http://cstheory.stackexchange.com/questions/21571/is-np-in-dtimenpoly-log-n/21660#21660  

---

## 0 answers

