Impossible and Impractical

When do we solve the really hard problems?

In computer science, there’s a category of problems that are simply impossible to solve. The Halting Problem is the canonical example, and it goes something like this:

You build a program, let’s call it Halt. It isn’t complicated, Halt simply determines whether another program will run forever in an infinite loop or it will eventually finish.

But then someone goes and writes a program called Trouble that looks at what Halt comes back with and does the opposite. So if Halt says Trouble will loop forever, Trouble does the opposite thing and finishes its run. If Halt says Trouble will finish, again it does the opposite and loops forever, never finishing.

Trouble is a perfectly legitimate program. It may not be trivial to write, but programming is all conditions and loops.

So what happens if Halt tries to evaluate Trouble? It can’t work.

Halt cannot exist. The Halting Problem cannot be solved. In CS lingo it’s undecidable.

Alan Turing came up with this around 100 years ago just as we were building the first computers. This is from the same guy who created the Turing Test, one of the more interesting questions in computer science until AI and Large Language Models came along and showed us just how easily we can be fooled.

As opposed to the impossible mind-bendy halting problem, impractical problems are ones we’d very much like to solve. But, the algorithms to solve them require so much compute that before we get an answer the sun will become a red giant and turn the Earth into a tater tot.

The classic example of an impractical problem is The Traveling Salesman. Again the problem is deceptively simple:

A salesman needs to visit 20 cities to hype his new AI app (which looks like juice boxes). What’s the most efficient route?

Picture by … AI

We solve this problem by checking each possible route. If the salesman is going to 5 cities you can do it. There are 120 possible routes. The math that counts all routes is 5 factorial or (5!).

5 x 4 x 3 x 2 x 1 = 120

You’ve heard of exponential. That’s growth by a constant factor, for example doubling every year. Perhaps you’ve also heard that when AI starts building AI it will grow exponentially smarter until … the SINGULARITY.

Factorial growth is significantly faster than exponential growth — every new city you visit increases the number of routes by a higher factor. Say the AI juice boxes are taking off, so now our salesman has to visit 10 cities. At 10 cities, the number of possible routes jumps from 120 to nearly 4 million.

Twenty cities? That’s over 2 quintillion or 2,432,902,008,176,640,000 possible routes.

The Traveling Salesman Problem isn’t impossible like the Halting Problem, but it’s impractical. Forty cities? It would take the world’s fastest computer hundreds of years to calculate every route. That’s really not so many cities — no juice box for you! In computer science, that’s called an intractable problem.

A heuristic is a clever workaround or hack that gets close to the right answer. For the TSP, just pick the closest city each step of the route. You won’t get the optimal answer but it’s close enough. That’s how your Amazon driver figures out where to drop off your monthly supply of Hanes boxer briefs.¹

I wrote a program that does the math — you can play with it here. ²

At the turn of the century, math enthusiast and businessman Landon Clay launched The Millennium Prize Problems. Seven unsolved problems. Solve one, win a million dollars. The TSP lives in one of these.

The world is full of problems to solve that would do more than deliver juice boxes. Or boxer briefs. Making progress on these could be big — we could live longer, happier lives on a healthier planet.

So how’s our great new innovation AI doing at solving these hard problems? AI isn’t going to save humanity by doing your homework or drawing weird pictures. Our AI salesman will tell you it will improve everything you do just a little bit. You’ll become more productive.

Every product I ever worked on promised this same thing. It’s impossible to quantify.

AI has taken a couple of swings:

Google’s AlphaFold made a major breakthrough in protein folding, accelerating biological research (like understanding Alzheimer’s) leading to a Nobel prize.

Another: AI helped decipher the carbonized Herculaneum scrolls that burnt up when Mt. Vesuvius erupted 2,000 years ago. So far they’ve found the word ‘purple’ and a discussion about the nature of ‘pleasure.’ Translation is ongoing. I’m certain more p-words will be found.

Perhaps we might also work on, say, the climate, Alzheimer’s, food for everyone.

How about we figure out fusion and cure cancer?

I don’t have a quintillion years.

1. The internet tells me Hanes Boxer Briefs are the bestselling item on Amazon. That’s just weird.

2. The program assumes you start at the first city. So if you’re visiting 5 cities, put in 6.