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

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

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.