# Best-case Running-time to solve an NP-Complete problem

What is the fastest algorithm that exists to solve a particular NP-Complete problem? For example, a naive implementation of travelling salesman is $O(n!)$, but with dynamic programming it can be done in $O(n^2 2^n)$. Is there any "easier" NP-Complete problem that has a better running time?

Note that I'm curious about exact solutions, not approximations.

-
There are a lot of NP-complete problems which are linear-time (or $n \log n$ time) reducible to 3-SAT (and vice versa). If one of these can be solved in $2^{O(n^\alpha)}$ time for $\alpha < 1$, they all can be. Most computer scientists think this is unlikely. – Peter Shor Jul 28 '10 at 0:24

If P is an NP-complete problem, then define Pk = instances of P in which the instances have been blown up from size n to size nk by padding them with blanks. Then Pk is also NP-complete, but if P takes time exp(p(n)) to solve where p is some polynomial then Pk can be solved in time essentially exp(p(n1/k)) (there's a little more time required to check that the input really does have the right amount of padding but unless the running time is polynomial this is a negligable fraction of the total time). So there is no "easiest" problem: for every problem you name this construction gives another easier but still NP-complete problem.

As for non-artificial problems: most hard graph problems like Hamiltonian circuit, that are hard when restricted to planar graphs, can be solved in time exponential in √n or in (√n)(log n) by dynamic programming using a recursive partition by graph separators.

-
Let me just add that the reparametrization phenomenon in the first paragraph is unavoidable even for "natural" problems. For example, the question itself asserts that travelling salesman is $O(n!)$ in the naive algorithm. However, if we simplify traveling salesman to the directed Hamiltonian path problem, then rigorously, as a function of the input length, the naive algorithm is actually $O(\sqrt{n}!)$ time. – Greg Kuperberg Nov 27 '09 at 21:10

If P = NP, then there is a polynomial-time algorithm for solving any given NP-Complete problem. Otherwise, it's known that there exist no general algorithms for any NP-Complete problem that are better than half-exponential: that is, f(x) where f(f(x)) is exponential.

-
Where is this result proved? It seems very surprising to me. Is what you're saying that the optimal algorithm for SAT might take $O(n^5)$ time, it might take $O(2^{\sqrt{n}})$ time, but it cannot possibly take $O(n^{\log \log n})$ time? Or am I misunderstanding your answer? – Peter Shor Jul 24 '10 at 14:11
I was thinking of Wigderson's result that a proof that DISCRETE-LOG can be solved in $O(f(x))$ time can be transformed into a proof that it can be solved in $O(\exp(f^{-1}(x))$. But this applies only to natural proofs in the sense of Razborov-Rudich, so I was wrong my claim. – Charles Jul 24 '10 at 21:40
Thanks. That result sounds interesting ... I'm going to have to look at it. – Peter Shor Jul 25 '10 at 15:26
It's cited in the Razborov-Rudich paper, I believe. I don't know if it's been published apart from that. – Charles Jul 25 '10 at 18:40