"this looks like a serious effort."

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 P≠NP problem actually solved? What did this mean for the field? And who cares anyway?

**What is P≠NP Anyway?**

^{2}.

*The New Yorker*cartoons. I love the one where a scientist has written on a blackboard:

^{2}

^{2}

- Problems that arise in optimization in many industrial settings.
- Problems that arise in cryptography and security.
- Problems that arise in simulations of all kinds: from protein folding, to simulations of complex physical systems, to simulations of mathematical systems.
- Problems …

*If Q is true, then there will never be algorithms for these problems that are much better than the obvious algorithms.*

**Why Care About Q?**

**Why Is Proving Q So Hard?**

^{2}again, which follows from the theory of Special Relativity. We know this equation is right: There are a myriad ways to "prove" it. From physical experiments, to the existence of nuclear power plants, to existence of atomic bombs, we now have proof that Einstein was right. Perhaps it is unfortunate he was right, but there is little doubt about this great equation.

- The equation E=mc
^{2}makes a positive prediction. - The limit that we cannot send signals faster than the speed of light is a negative prediction.

## §

**Act I: A "Proof" Is Announced**

The proof of Deolalikar was sent out last weekend to a select group. Quickly, the proof with additional comments moved around the net via email. I decided to look at the paper and make a short post about the claimed proof. Greg Baker of Simon Fraser made the first post on the proof, and he had included a copy of the paper.

**Act II: Enter the Heavy Hitter**s

*Nature*were involved as were other more popular publications such as

*Forbes*and

*The New York Times*. For example, I wound up talking on background with John Markoff of the

*Times*and Ken did likewise with Lee Gomes of

*Forbes*.

- If Q is false, then D is true.
- But D contradicts known—to the experts —facts about certain complex physical systems.

**Act III: Flaws**

**And on …**

*Groundhog Day*. My day is gone, I am still not reading my book. Again I am writing a post about Deolalikar's proof—actually two posts—the other is a technical one for my blog. I still do not know if the proof is correct or not, but I believe that I have learned a lot this week. I learned a potentially new approach to Q from Deolalikar, I learned that many, many people care about Q, and I learned that the Internet may not replace referees yet, but it can raise many important questions in a positive and constructive manner. I also decided—not learned—that next Sunday I will

*not*be writing a post on this proof. At least that is my plan.

*The author, Richard J. Lipton of the College of Computing at Georgia Tech, has a*

*blog*

*on complexity theory and mathematics. Selected posts from its first year, 2009, are due out this autumn as a book published by Springer-Verlag. He would also like to thank Ken Regan for many helpful comments on this post.*

## Join the Discussion (0)

## Become a Member or Sign In to Post a Comment