It’s time for my bimonthly self-promotional horn toot. The new issue of American Scientist is now available online, and paper copies should soon be stuffing mailboxes everywhere. My “Computing Science” column is on a new class of “holographic” algorithms invented a few years ago by Leslie G. Valiant of Harvard. The ideas have been further developed by Jin-Yi Cai of the University of Wisconsin (who is currently visiting Harvard as a Radcliffe Fellow) and several students and colleagues both at Wisconsin and in China.
If you want to know what holographic algorithms are all about, you’ll have to go read the column. I’m not going to rehash it here. Instead, I’m going to recycle a few paragraphs of a version of the column that might have been but never will be. This was a false start, an attempt at a lead that wound up leading me in the wrong direction:
It was the final day of a workshop, and I joined a group for dinner at a farmhouse restaurant in the village of Muggia, around the corner from Trieste, where Italy meets Istria. As the evening was winding down, we sat drinking the last of the wine, watching the sun sink into the Adriatic, and debating the P = NP question. The debate was somewhat lopsided: No one at the table was willing to defend the proposition that P is indeed equal to NP. But there was plenty of room for argument between hard-liners who insisted that P is most certainly not equal to NP and those who took a more agnostic view.
What are P and NP? They are classes of computational tasks or problems. Roughly speaking (I’ll try to speak less roughly in a moment), the class P includes all the things we know how to compute quickly. NP is a larger class, encompassing all the problems known to be in P and many others besides; for these additional tasks we don’t have efficient algorithms, and yet no one has proved that such algorithms don’t exist. If it should turn out that P = NP, then thousands of seemingly hard problems actually have some quick shortcut solution, if only we could find the secret.
A mathematician at my end of the table took an inflexible position: P = NP is not only wrong but unthinkable—a notion akin to time travel or perpetual motion. I had been lurking silently through most of this conversation, but at this point I spoke up. Time travel seems implausible, I said, because it would undermine causality, and perpetual motion would violate the conservation of energy. What bedrock principle would be overturned by the discovery that P = NP? The mathematician replied: “Do you believe in miracles? No? Well, wouldn’t it be miraculous if we lived in a universe where every last one of those NP problems has an easy solution?”
This was good enough for me on that mild summer night in Muggia. The fact is, however, the miracle argument cuts both ways. There’s a subclass of NP problems, designated NP-complete, with a special property: If there’s an efficient algorithm for any one of these tasks, the same method can be used to solve all NP problems efficiently. Thus for P to be different from NP requires the “miracle” that not even one out of thousands of NP-complete problems has a quick solution….
One more note on the column. This is difficult subject matter, and my grasp of it is tenuous. I could not have written the piece without a lot of help and hand-holding from Valiant and Cai, who were reading drafts and answering phone calls up until the very moment the issue went to press. I have a reason for thanking them here rather than in the column itself: If I’ve goofed in spite their efforts, I don’t want them implicated.