I’ll admit it’s probably the “strangest” math I have ever done. It is hard to understand in as brief a statement as I made (even if I was the best at explaining said topic in the world, and I’m not), so don’t feel bad. I’ll gladly take the blame for being confusing

I’ll try again, though…

NP-complete problems are not just “maths that takes long to calculate”, they are “problems for which the time required to solve grows non-linearly as the problem size increases.” You can look up the formal definition if you wish.

But another way to prove a problem is NP-complete is through reduction. I will now attempt to make this clear and tie it to the consequences I stated before.

First, we need to discuss time-complexity (how long it takes an algorithm to complete, usually estimated in terms of the problem size). If our problem size is defined by n, and our time-complexity is defined as (n^n + 100*n), then as we grow n to very large numbers the result will be governed by the n^n term and the 100n term will not really be important. Thus we would say the time-complexity of this problem is O(n^n) (this is “Big-O” notation). This is a simplification, but a justified one. We only care about the 100n term if comparing to another O(n^n) algorithm/problem.

In my opinion, the concept of “reduction” is the hardest point to grasp because it’s very abstract and situational since we are potentially talking about quite different problems at first glance. The idea of reduction is nicely illustrated here:

Let’s say we have 2 problems/algorithms:

A: NP-Complete

B: ???

We could apply the definition of NP-complete directly to assign classification to B, but it’s usually easier to try reduction. If B is NP-complete, then we will be able to reduce A to B and B to A, both using procedures that require linear time. Just as my example in describing time-complexity, the reduction procedures end up being insignificant given big n since both problems require non-linear time to solve. Both become (linear + non-linear = non-linear).

We know that P is a subset of NP. We can reduce a P problem to an NP-complete problem (pointless as that would be, since the time-complexity gets worse), but we don’t know how to reduce an NP-complete problem to a P problem in linear time. Such a method might exist (it has not been proven impossible), but we don’t know it. Thus we just don’t know if P = NP.

If P does equal NP then we know (by definition) that we can reduce NP problems to P problems using linear time reductions. So then solving an NP problem is just reduce to a P problem and solve. The time-complexity would be (linear + linear = linear). So if you devise an algorithm/procedure that solves the traveling salesman problem in linear time, you have solved all NP-complete problems in linear time and proven that NP = P.

TL;DR

Don’t bother trying to solve the general traveling salesman problem in linear time… it’s impossible or among the hardest problems anyone has considered.