Generally most np complete problems seem to have the best strategies operate in time $O(c^n$) for some choice of $c$

Has something like $O(2^\sqrt{n})$ (or any other less than exponential but greater than polynomial running time) ever been encountered in the wild as a run time for an algorithm that solves an NP complete problem?

  • $\begingroup$ According to the ETH np-complete problems does not have $2^{o(n)}$ time complexity. $\endgroup$ – Mohsen Ghorbani Sep 27 '19 at 17:22
  • 1
    $\begingroup$ No, the ETH refers only to SAT, not to all NP-complete problems. $\endgroup$ – Hermann Gruber Sep 27 '19 at 17:39
  • $\begingroup$ Yes my bad... but I think there are not known np-complete solvable in $2^{o(n)}$, also padded version of SAT(or any npc) has the property you want. $\endgroup$ – Mohsen Ghorbani Sep 27 '19 at 18:10

The maximum clique problem on graphs with $m$ edges is solvable in time $2^{O(\sqrt m)}$. See Lemma 11.6 in F. Fomin and D. Kratsch, exact exponential algorithms, Springer, 2010. Also, note that PLANAR 3-SAT, while NP-complete, is solvable in time $2^{O(\sqrt n)}$, where $n$ denotes the number of vertices: https://cstheory.stackexchange.com/questions/30883/are-there-subexponential-algorithms-for-planar-sat-known


Suppose there is a $O(2^n)$ time algorithm for set $L$ and $L \in NP-complete$. define $L'=\{1^{n^c-n}l| l\in L\& |l|=n \}$ it is easy to prove that $L' \in NP-complete$ and there is a $O(2^{\sqrt[c]{n}})$ time algorithm for $L'$. On the other hand according to ETH $SAT$ can't be solved in time $2^{o(n)}$ and it is enough to conclude that there are no $NP$-complete such that solvable in time $n^{poly(\log n)}$. The best known algorithm for 3-SAT is in time $1.3^n$ or at least near this number.


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.