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.
 A: 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.
A: 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.
