# Is the fastest solution for one NP-Complete problem the fastest solution for all NP-complete problems?

This answer seems incorrect to me:

Which NP-Complete problem has the fastest known algorithm?

The fastest solution for one NP-Complete problem should be the fastest solution for all NP-Complete problems.

Why?

Can any NP-complete problem be reduced to any other NP-Complete problem in polynomial time?

So, finding some super-optimal exponential time solution, $$O(1.27k + nk)$$, should be able to be applied to all NP-Complete problems. In other words, the most optimal solution is the same for all NP-Complete problems.

A polynomial-time reduction only needs to preserve the size of the problem up to a polynomial upper bound (which is implied by the time constraint).

As an example, suppose you have two NP-complete problems and $$A \le_p B$$, the reduction blows up the instance size from $$n$$ to $$n^2$$, and $$B$$ admits an algorithm with running time $$2^\sqrt{n}$$. This only induces an algorithm for $$A$$ with a running time of $$2^{\sqrt{n^2}}=2^n$$.

• This is great. So, some NP-hard problems have will have a slightly faster runtime (still exponential) than others. Simply reducing all NP-hard problems to the NP-hard problem with the fastest runtime might not yield the expected faster results as the reduction itself can increase the runtime a good deal? Oct 7, 2020 at 16:55
• @Matthaeus If we want to be precise, it's possible that P ≠ NP but the fastest algorithm for an NP-complete problem is superpolynomial but subexponential. This cannot be ruled out by P ≠ NP alone. But yes, what you wrote is basically correct otherwise. Oct 7, 2020 at 19:29

Here is a way to see that there could be arbitrarily large differences between the optimal time complexities of different NP-complete problems.

Suppose P = NP. Then any problem in P with at least one accepting input and at least one rejecting input is NP-complete. By the time hierarchy theorem, there are problems that take $$\Theta(n)$$, $$\Theta(n^2)$$, $$\Theta(n^3)$$, ... time to solve and cannot be solved significantly faster. So if P = NP, then there are NP-complete problems that have asymptotic time complexities of all polynomial exponents (ignoring some log factors in the time hierarchy theorem).

Let's say the NP complete problem A can be solved in O(f(n)), where n is the problem size. And B can be solved in O(g(n)), where g is much larger than f. If we reduce an instance of B to an instance of A, the problem size is very unlikely to stay unchanged. Lets say the problem size is changed from n to h(n), and the time used for the reduction is negligible.

Then solving he instance of B by reducing it to an instance of A will take O (f(h(n))), which may very well be a lot larger than O(g(n)). For example, if both A and B can be solved in O(c^n) for different fixed c > 1, and the reduction changes the instance size from n to n^2, then the reduction will result in a much slower solution.

So your assumption is completely wrong. 1.27^3 > 2, so if you have a problem that can be solved in O(2^n), and you use a reduction to your O(1.27^n) problem that increases the instance size just by a factor 3, the reduction leads to a slower algorithm.