HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Are there any NP complete problems in SUB EXP TIME?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
areanyexpsubproblemstimecompletethere

Problem

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?

Solution

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

Context

StackExchange Computer Science Q#115167, answer score: 7

Revisions (0)

No revisions yet.