The road less promising

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 this particularly hard set of problems (known as NP-complete) in a reasonable amount of time. A reasonable amount of time means less than a billion years.

One example is the so-called Traveling Salesman problem. What is the most efficient route a traveling salesman can take to visit all the cities in his sales area, (efficient meaning the least amount of driving time)? 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, or whenever you go on a run of errands and want to be efficient with your driving time.

The Holy Grail algorithm would make this optimization problem tractable. No one knows if it exists. No one has been able to prove that it doesn’t, though they’ve tried. What we do know is that if a solution is found to any of the NP-complete problems, we’ll be able to solve all of them. That would mean instant fame, fortune and a shiny pedestal in computer history.

I once worked for an eccentric and brilliant Computer Science professor (let’s call him Ben) who was determined, in his own way, to find the Holy Grail algorithm. Ben 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, Ben had developed ingenious methods for getting computers to learn. He made money on the stock market with an automatic trading AI he’d written. He 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 and thousands of games. Most chess-playing AIs are pre-programmed with sophisticated models of chess strategy.

Yet despite all his practical successes in Artificial Intelligence solving heuristic problems that demanded merely excellent solutions as opposed to optimal ones, Ben had Holy Grail on the brain. He was obsessed with a particular NP-complete problem known as the 8-puzzle or N-puzzle, the old sliding tile game where you have to slide the scrambled tiles back into order. Ben 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 8-puzzle and thereby find the Grail.

Of all my time spent working in Computer Science, it was probably the series of months I spent working with Ben, searching for the Holy Grail algorithm, that led me to realize it wasn’t the field for me. This is not to say it wasn’t time well-spent. I actually loved the work. 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 Ben was illuminating, and I think it’s a story worth sharing.

We would meet once a week or so. In order to gain some new foothold in solving the 8-puzzle – which begins in a random state and ends up in exactly one solution state – I must have dreamt up and coded a million 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 sort of like being trapped inside a garden maze with someone calling to you from the exit. You follow the sound of the voice and seem to be making headway, but over and over you come to a dead end that stops just short of the exit. So you turn around and try a different route. 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 Ben 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 Ben’s window. Every ten minutes or so, an enormous redwood tree would come crashing down. They were clearcutting to make room for the brand new Engineering building. As it fell, each tree made the most horrific moaning sound, something like a blue whale dying, not a redwood. I made a remark about the beautiful and sad old trees. Ben turned and looked out the window.

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

Later that week, I’d be up at night coding our latest wizardry, some little algorithmic sleight-of-hand we’d dreamed up. As always, without fail, another flaw in our reasoning would stare back 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 Ben secretly knew our Holy Grail search was futile. Was he playing a sophisticated joke on me? Was the 8-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. And you know what? It didn’t look promising. A waste of computation, really.