Hard in Theory, Solved in Practice

The travelling salesman problem is the emblem of intractability. Visit a set of cities once each, return to the start, make the total distance as short as possible. It is NP-hard, which is the standard shorthand for hopeless, and it appears in every popular account as the thing computers cannot do.

An exact solver has proved the shortest possible route through a real instance of 85,900 points, arising from a chip layout problem at Bell Labs, and it has done the same for every instance in the standard benchmark library.

Both of those sentences are true and people find the combination hard to hold. The resolution is that worst-case hardness and practical hardness are different measurements, and the first makes no promises about the second.

A hardness result is a statement about all inputs, including adversarial ones. It says: there is no method that is efficient on every instance, including the instances designed by somebody who has read your method and wants it to fail. That is a strong and useful thing to know. It is not a statement about the instance on your desk, which was produced by a chip layout, a delivery schedule or a telescope scheduling constraint, and which has structure in it.

What exact solvers do with that structure is prune. Rather than enumerating routes, they compute a bound on how good any route in a whole family could possibly be, compare it against the best route found so far, and discard the entire family without examining a single member. Do that recursively and you can prove optimality while having looked at a vanishing fraction of the possibilities. This is not a trick that evades the theory; it is the theory applied to inputs that happen not to be adversarial.

Alongside the exact solvers there is a second category, and the distinction between its two halves matters.

An approximation algorithm runs quickly and comes with a stated bound: this route is never worse than so much above optimal. The bound is the product. It is a theorem, it holds for every input, and it lets you make a decision about whether the answer is good enough.

A heuristic in the loose sense runs quickly and offers no bound. It may be excellent. It frequently is. What it cannot tell you is how wrong it might be on the input you have, which means you are trusting it rather than knowing something.

The cleanest illustration of the whole tension is the simplex method for linear programming. Its worst case is exponential, and instances that trigger the worst case have been constructed deliberately, by people looking for them. It has also been the workhorse of industrial optimisation for seventy years, running airline schedules, refinery blending and supply chains, because the inputs that businesses actually have do not look like those constructions.

Two true statements in tension, both load-bearing. The theorem is about every input. The practice is about the ones that arise.

Which gives a rule for reading claims in this area. When somebody says a problem is NP-complete, they have told you something real about the class of all inputs and nothing yet about yours. The follow-up question is always the same: what do your instances look like, and has anybody tried.