-1

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

Nikos M.
  • 581
  • 2
  • 9
  • 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

1 Answers1

7

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)$.

Austin Buchanan
  • 1,166
  • 1
  • 17
  • 28
  • +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. Jun 13 '14 at 19:32
  • 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
  • 2
    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