A Waste of Computation

I used to be a computer scientist. I could respectably program in more than ten languages. I pondered the theoretical limits of computation and ways to overcome or exploit them. I tinkered solutions to arcane problems in artificial intelligence. For a short time, I even searched for the Holy Grail.

You see, there’s a kind of Holy Grail in computer science. No one has been able to write an algorithm that can compute solutions to a particularly hard set of problems (known as NP-complete) in a reasonable amount of time. A reasonable amount of time means less than a trillion years or so.

One example is the so-called Traveling Salesman problem: what is the one most efficient route a traveling salesman can take to visit all the cities in his sales area using the least amount of gas? You can figure out the optimal route for a handful of cities, but as soon as you get above ten or so, the complexity of the problem grows astronomical. Analogous problems show up for routing traffic on the internet, routing airplanes between airports, coloring world maps, and whenever you go on a run of errands and want to be efficient with your driving time.

Computer scientists have found plenty of algorithms that approximate the optimal solution. That is, they compute solutions that are Merely Excellent but not The Best. One thing you should know about computer scientists, though, is that they are obsessed with optimality. And the Holy Grail algorithm would make this optimization problem tractable. No one knows if it exists. And no one has been able to prove that it doesn’t exist (though they’ve tried). What we do know is that if an algorithm is ever found to solve any one of the NP-complete problems, we’ll be able to solve all of them in one fell swoop. They are equivalent to each other. That’s why it’s generally considered to be the most important open question in mathematics and tops the list of the Millenium Prize unsolved problems. Finding the Holy Grail algorithm would mean instant fame, fortune and a shiny pedestal in history for the discoverer.

Promising paths

I once worked for an eccentric and brilliant Computer Science professor named Bob who was determined, in his own way, to find the Holy Grail algorithm. Bob had a hilarious sense of humor, was a great teacher, and could read Yoga sutras in the original Sanskrit. Working in the field of Artificial Intelligence, Bob had developed ingenious methods for getting computers to learn. He’d made money on the stock market by writing an automatic stock-trading AI. He’d created a chess playing AI that started out with zero knowledge of the game but learned to play respectable chess after losing (and learning from) thousands of games. (Most chess-playing AIs are pre-programmed with sophisticated chess strategies by their human creators. They don’t have to learn the hard way.)

Yet despite all his practical successes solving problems that demanded merely excellent solutions (as opposed to optimal ones), Bob had Holy Grail on the brain. He was obsessed with a particular NP-complete problem known as the N-puzzle; you’re probably familiar with the 8-puzzle version, the old sliding tile game where you have to slide the 8 tiles scrambled on a 3×3 grid back into order. The N-puzzle is the general case of the 8-puzzle for a grid of any size. Bob felt that existing algorithms weren’t making optimal use of past experience — they were ignoring valuable lessons learned in the early stages of problem solving that could more quickly lead to a solution later on. He called it a waste of computation. And he was convinced he could discover a new path to solving the puzzle and thereby find the Grail.

Of all my time spent working in Computer Science, the months I spent working with Bob, searching for the Holy Grail algorithm, showed me most clearly that it wasn’t the field for me. That’s not to say it wasn’t time well-spent. I loved the work and always looked forward to our next meeting. It was fascinating and fed the part of me that sought beauty in the mathematical and abstract. I just eventually came to the conclusion that I was more interested in human beings than computers. And of course, I continue to be fascinated by the combination of the two. Still, my time with Bob was illuminating, and I think it’s a story worth sharing.

We would meet once a week or so. In order to discover some new foothold for solving the N-puzzle — which begins in a random state and ends up in exactly one solution state — we dreamt up (and I programmed) myriads of ways to map out its strange, mountainous landscape; to find a way to see the end from wherever you happened to be starting from. It’s like being trapped inside a garden maze with someone calling to you from the exit. You can follow the sound of the voice and know you are getting closer; you pick routes that seem to head in the right direction, but over and over you come to a dead end that stops just short of the exit. So now you have to backtrack and try a different route, one that didn’t look as promising the first time you saw it. In other words, the voice calling to you is not enough. You need to be able to look down a path without walking down it and somehow know if it’s promising or not. If you can figure out a way to do that, you’ve solved NP-complete and found the Holy Grail.

Each meeting with Bob went much the same. I would share what I’d tried that week and point out the flaw I’d discovered in our earlier reasoning. Over the course of an hour, we’d inevitably have a leap of insight into a promising new technique to try out. We were back on the brink of Eureka! As the meeting wound down, the conversation would drift… to chess, metaphysics, Sanskrit, stock market prediction, yoga, or the philosophy of J. Krishnamurti.

One afternoon in his office, we sat talking while chainsaws buzzed gratingly outside Bob’s window. Every ten minutes or so, an enormous redwood tree would come crashing down not fifty yards from where we sat. They were clear cutting a redwood grove to make room for the new Engineering building. As it fell, each tree made the most horrific and tortured moaning sound, what seemed more like a blue whale’s death rattle than a majestic tree. I made a remark to Bob about the beautiful and sad old trees. Bob turned and looked out the window.

“I know, it’s terrible. What a waste of computation.”

Later that week, I was up all night, coding our latest wizardry, some little algorithmic sleight-of-hand we’d dreamt up. Inevitably, another flaw in our reasoning stared back at me from the terminal screen in the strange half-light of dawn. Another devil in the details. Another promising path that dead-ended just short of the exit.

The weeks slid by. During the drifting, philosophical epilogues to our meetings, I began to wonder if Bob secretly knew our Holy Grail search was futile. Was he playing a sophisticated joke on me? Was the N-puzzle merely a kind of algorithmic Zen koan intended to reveal the limits of my own mind, in order for me to let go of it? Was our collaboration an allegory for the futility of striving after rational answers to absurd questions? Was he trying to tell me that life was purposeless?

After precisely one too many of those Holy Grail nights, I found myself at a crossroads. I took a good long look down the path I was about to take — without walking down it: there I saw my future life as a computer scientist, hunched over my desk, alone, twiddling bits through the long night. And you know what? It didn’t look promising.

A waste of computation, really.