# 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 it is travelling salesman problem,that graph can be decomposed small known graph which computer have already calculated. – Takahiro Waki Nov 14 '15 at 16:03

• 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
• 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