Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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?
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.
