# Any result connecting an NP-complete problem with slight super-polynomial time?

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

• huh, why not? P≠NP follows QED – vzn Jun 13 '14 at 18:17
• @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. Jun 13 '14 at 18:38
• oh you mean an upper bound? – vzn Jun 13 '14 at 19:08
• @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 – Nikos M. Jun 13 '14 at 19:11

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)$.
• So as $k$ tends to infinity, it becomes polynomial, correct? – Nikos M. Jun 13 '14 at 19:34
• 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. Jun 13 '14 at 19:37
• The naive algorithm is to remove all isolated vertices and then try all possible subsets of the $n^{1/k}$ remaining vertices. – Austin Buchanan Jun 13 '14 at 19:48