What is the fastest algorithm that exists up with 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 perhaps "easier" NP-Complete problem that has a better running time?
I'm curious about exact solutions, not approximations.
A characteristic of the NP-Complete problems is that any of the problems in NP can be mechanically transformed into any of the NP-Complete problems in, at most, polynomial time.
Therefore, whatever the best solution for any given NP-Complete problem is, it is automatically a similarly-good solution for any other NP problem.
Given that dynamic programming can solve Traveling Salesman Problem in 2^n time and 2^n space, the same must be true of all other NP problems [well, plus the time to apply the transformation, I guess - so it could be 2^(n+1)].
[...] with dynamic programming it can be done in O(n^2 * 2^n). Is there any perhaps "easier" NP-Complete problem that has a better running time?
Sort of. You can get rid of any polynomial factor by creating an artificial problem that encodes the same solution in a polynomially larger input. As long as the input is only polynomially larger, the resulting problem is still NP-complete. Since the complexity is by definition the function that maps input size to running time, if the input size grows the function gets into lower O classes.
So, the same algorithm running on TSP with the input padded with n^2 useless bits, will have complexity O(1 * 2^sqrt(n)).