<p>You might need to be more specific as to what "slightly super-polynomial" means. But, this might work: you can take an NP-complete problem, and pad it. </p>

<p>For example: for any constant $k\ge 1$, $n$-vertex instances of CLIQUE remain hard when only $n^{1/k}$ of the vertices have positive degree (e.g., take an instance $G=(V,E)$ of CLIQUE and add $|V|^{k}-|V|$ isolated vertices to it). These instances of CLIQUE can be solved in time $2^{n^{1/k}}\text{poly}(n)$. </p>

CC BY-SA 3.0
2014-06-13T19:32:49.463Z
+1, ahh nice, assume this is *very slight super-polynomial*. Indeed the exact *threshold* of *slight* super-polynomial is not specified. Intuitively it is super-polynomial but sub-exponential, the exact threshold is part of the question itself. Will wait for other answers also
Nikos M.
CC BY-SA 3.0
2014-06-13T19:34:30.297Z
So as $k$ tends to infinity, it becomes polynomial, correct?
Nikos M.
CC BY-SA 3.0
2014-06-13T19:37:39.163Z
In the meanwhile, if you would like to elaborate a little more on how the $2^{n^{1/k}}+ \text{poly}(n)$ complexity is computed for this CLIQUE problem, or add some reference would be very nice.
Nikos M.
CC BY-SA 3.0
2014-06-13T19:48:25.230Z
The naive algorithm is to remove all isolated vertices and then try all possible subsets of the $n^{1/k}$ remaining vertices.
Austin Buchanan
CC BY-SA 3.0
2014-06-13T19:28:08.610Z
2014-06-13T19:50:26.140Z
2014-06-13T19:50:26.140Z
Austin Buchanan
<p>Helo everybody, </p>

<blockquote>
  <p>is there any result or research that connects some $NP$-complete problem
  with only <em>slightly</em> super-polynomial (strongly sub-exponential) time?</p>
</blockquote>

<p>This would not necessarily involve the $P$ vs $NP$ problem (which i stand on $P=NP$, anyway).</p>

<p>Thank you</p>

CC BY-SA 3.0
2014-06-13T18:17:17.693Z
huh, why not? P≠NP follows QED
vzn
CC BY-SA 3.0
2014-06-13T18:38:17.943Z
@vzn, not necessarily if it does not provide separation between P and NP, for example a result that an np-complete problem can be solved in slightly super-polynomial time, does not exclude a polynomial algorithm
Nikos M.
CC BY-SA 3.0
2014-06-13T19:08:41.463Z
oh you mean an _upper_ bound?
vzn
CC BY-SA 3.0
2014-06-13T19:11:24.467Z
@vzn, yes it can also be an upper bound, or an actual algorithm that runs in slightly super-polynomuial time, both do not exclude polynomial algorithms. If you are interested, check this [other question of mine](http://cstheory.stackexchange.com/questions/24879/easier-and-harder-instances-of-np-complete-problems)
Nikos M.
<polynomial-time><np-complete>
Any result connecting an NP-complete problem with slight super-polynomial time?
Nikos M.
# Any result connecting an NP-complete problem with slight super-polynomial time?

(Asked by: username_0 on 2014-06-13)

Helo everybody,

> is there any result or research that connects some $NP$-complete problem
> with only *slightly* super-polynomial (strongly sub-exponential) time?

This would not necessarily involve the $P$ vs $NP$ problem (which i stand on $P=NP$, anyway).

Thank you

**Tags:** polynomial-time, np-complete

> **Comments:**
> **username_1**: huh, why not? P≠NP follows QED  
> **username_0**: @username_1, not necessarily if it does not provide separation between P and NP, for example a result that an np-complete problem can be solved in slightly super-polynomial time, does not exclude a polynomial algorithm  
> **username_1**: oh you mean an _upper_ bound?  
> **username_0**: @username_1, yes it can also be an upper bound, or an actual algorithm that runs in slightly super-polynomuial time, both do not exclude polynomial algorithms. If you are interested, check this [other question of mine](http://cstheory.stackexchange.com/questions/24879/easier-and-harder-instances-of-np-complete-problems)  

---

## 1 answers

### Answer by username_2 on 2014-06-13. Score: 7 | Accepted answer

You might need to be more specific as to what "slightly super-polynomial" means. But, this might work: you can take an NP-complete problem, and pad it.

For example: for any constant $k\ge 1$, $n$-vertex instances of CLIQUE remain hard when only $n^{1/k}$ of the vertices have positive degree (e.g., take an instance $G=(V,E)$ of CLIQUE and add $|V|^{k}-|V|$ isolated vertices to it). These instances of CLIQUE can be solved in time $2^{n^{1/k}}\text{poly}(n)$.

> **Comments:**
> **username_0**: +1, ahh nice, assume this is *very slight super-polynomial*. Indeed the exact *threshold* of *slight* super-polynomial is not specified. Intuitively it is super-polynomial but sub-exponential, the exact threshold is part of the question itself. Will wait for other answers also  
> **username_0**: So as $k$ tends to infinity, it becomes polynomial, correct?  
> **username_0**: In the meanwhile, if you would like to elaborate a little more on how the $2^{n^{1/k}}+ \text{poly}(n)$ complexity is computed for this CLIQUE problem, or add some reference would be very nice.  
> **username_2**: The naive algorithm is to remove all isolated vertices and then try all possible subsets of the $n^{1/k}$ remaining vertices.  

---

