Einstein And The P≠NP Question
A post in CACM on the claimed P=NP proof
Moshe Vardi is the editor-in-chief of the CACM. He has done a great job in the last few years changing the publication and making it one of the great ones in Computer Science. He also the “Vardi” in the Immerman-Vardi Theorem.
Today I just one to thank him for the chance to write a guest post a week ago. I thought you may not have seen it and might want to read it.
The post was on the claimed proof of PNP and the first few hectic days looking at it. I was charged by Moshe to try and write a very non-technical piece on why PNP is such an important problem. I will give you a “taste” of the post and read here if you wish to see all of it. It is not technical by choice, so do not expect any new insights on the claimed proof. I do, however, hope you will like how I explain the problem.
The CACM Post
Last Sunday I planned to relax and read a book when I made the mistake of checking my email—never check your email on a Sunday. Among the usual messages was one from the eminent logician Harvey Friedman. It contained an attachment from Vinay Deolalikar, a researcher at Hewlett-Packard Labs in Palo Alto. The attachment was a 100+ page paper that looked serious, was serious, and had the elegant and short title “PNP.” In addition, the email contained a quote from Steve Cook on Deolalikar’s paper , which said,
“this looks like a serious effort.”
Steve is a Turing awardee, a winner for discovering the very same PNP problem. He—a logician at heart—is very careful, and for him to say the word “serious” made it clear that I would not be relaxing nor reading any book that Sunday. I would be working hard to try and figure out whether this was really a serious effort or not.
I write a blog, along with about 126 million people who do the same. Mine is on complexity theory, and so this claim was something that I felt I needed to write about. There are several other blogs on complexity theory: the best and most famous are Scott Aaronson’s blog, Lance Fortnow and Bill Gasarch’s blog, and Terence Tao’s blog . Even though I knew they would be discussing Deolalikar’s paper, I felt I could not avoid getting involved—my blog after all has “PNP” in its title.
My Sunday was gone, and as it turned out, so was the rest of the week. I kept reading the paper, sending and getting emails, and writing posts: all in an effort to report on what the theory community was doing to understand the claimed proof. Was the famous PNP problem actually solved? What did this mean for the field? And who cares anyway?
Perhaps the biggest surprise was that a lot of people do care. One lesson we learned is there are hundreds of thousands of people who were interested, there were hundreds of people who were willing to write thoughtful comments, and there were a number of superstar mathematicians and theorists who were willing to work hard to get to the truth of what Vinay Deolalikar claimed.
What is PNP Anyway?
The rest is here
If you read the post do you like the analogy to ?