Hitesh U Vaidya (@hiteshvaidya2) asked a thought-provoking question.

Q: Will machine learning prove useful in solving NP Complete problems?

A: The short answer is “If you’re an engineer, yes. If you’re a mathematician, no.” but there’s more to it.

“Solving” a problem means something very different to a mathematician than to an engineer. To oversimplify: A mathematical solution is complete, perfect and provable. An engineering solution is any approach that works pretty well most of the time. It’s a heuristic - a glorified hack that has proven itself useful. For NP-Complete problems, machine learning falls into this second category.

To illustrate the difference, picture yourself outdoors on a moonless night with nothing but a GPS altimeter. Your goal is to find whether any point in a fenced field is at an elevation higher than a thousand meters. You can’t see more than a step in any direction.

An engineering solution is to walk upslope to the top of whatever hill you're on. You can also wander around the field at random in hopes of discovering other hills that you can summit.

If you’ve looked around for a while and all you've found are gently rolling hills a few meters high, then you can reasonably conclude that the terrain probably stays under a thousand meters. But this isn’t good enough for a mathematician. Until you check every spot on the field, you don't know if there’s a narrow tower somewhere jutting up into the sky. A good mathematical solution would also be able to bound how long it will take to repeat this in a new field.

A problem can be solved in one sense, but not the other. The decision version of the Traveling Salesman problem (the poster child for NP-Complete problems) doesn’t have a mathematically provable solution, but there are tricks for finding engineering approximations quickly. On the other hand, the solution to nothing less than intelligence itself has been proven (under some assumptions), however we are still very far from an engineering implementation.

*There is precedent for engineering solutions paving the way for the math. PD-control of manufacturing robots had been implemented in production lines long before it was proved to be stable. Its practical success motivated mathematical work on the problem and inspired key insights. In this way, machine learning may yet be able to help make progress on mathematically solving NP Complete problems.

Thanks for the question Hitesh!