# Are there any NP complete problems in SUB EXP TIME?

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?

• According to the ETH np-complete problems does not have $2^{o(n)}$ time complexity. – Mohsen Ghorbani Sep 27 '19 at 17:22
• No, the ETH refers only to SAT, not to all NP-complete problems. – Hermann Gruber Sep 27 '19 at 17:39
• 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. – 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.