What is the best time to resolve NP-Complete?

Question

What is the fastest algorithm that exists to solve a specific NP-Complete problem? For example, a naive salesman implementation is O (n!), But with dynamic programming this can be done in O (n ^ 2 * 2 ^ n). Is there perhaps a simpler NP-Complete task that has a better run time?

I am interested in exact solutions, not approximations.

Answer 1

[...] with dynamic programming, this can be done in O (n ^ 2 * 2 ^ n). Is there perhaps a simpler NP-Complete task that has a better run time?

Grade. You can get rid of any polynomial factor by creating an artificial problem that encodes the same solution in a polynomial larger input. As long as the input is only polynomially larger, the resulting problem is still NP-completed. Since complexity is, by definition, a function that displays the size of the input during working hours, if the size of the input increases, the function goes to lower O classes.

So, the same algorithm that runs on a TSP with an input padded with n ^ 2 useless bits will have complexity O (1 * 2 ^ sqrt (n)).

Answer 2

The characteristic of NP-complete problems is that any of the NP-problems 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, it is automatically the same solution for any other NP problem.

Given that dynamic programming can solve the traveling salesman problem in 2 ^ n time and 2 ^ n space, the same should be true for all other NP problems [well, plus the time to apply the transformation, I think it could be 2 ^ (n + 1)].

Answer 3

As a rule, you cannot find the optimal solution for the general problem of Traveling Salesman without trying to use all the combinations (there may be negative distances, etc.).

By adding additional restrictions and relaxing the requirement of getting the best solution, you can speed things up a bit.

For example, you can get a polynomial executable time if the distances in the task obey "no longer go straight from A to B, and not from A to C to B" (i.e. the shortcut never lasts longer) and you can live with the result maximally exceeding the optimal value by 1.5 times. See http://en.wikipedia.org/wiki/Travelling_salesman_problem#Metric_TSP