A story of the rise and fall of a serious attempt at a proof that P$\neq$NP

Ed Nelson is a senior faculty member of the famous Princeton Mathematics Department. He is well known for his work in a number of areas, including logic and probability theory. Nelson, in 1950, created a beautiful problem about coloring the plane, not coloring a graph, coloring the whole Euclidean plane.

What is the fewest number of colors sufficient for coloring the plane so that no two points with the same color are a unit distance apart?

See this for more details on Ed’s problem.

Today I want to talk about what it might be like to have someone solve P=NP. Back in the mid 1990′s Nelson had an approach to proving P${\neq}$NP, that looked promising, and created quite a stir at Princeton. The question is: what will it be like to solve P=NP? In Ed’s case he thought for a while that he had a proof that P${\neq}$NP. The proof was based on some insights that he had from his previous work in logic. While the proof did not work, it did teach us a few things about what might happen if someone really solved the problem.

The Claim

One day, at Princeton, Andy Yao grabbed me and told me that Ed Nelson had a draft of a proof that P${\neq}$NP. I was excited of course, and asked Andy if he had checked the proof yet. Andy said that the paper was still a very rough draft, it had missing sections, and since he had just started to look at it, would I like to help him figure out what was up? I immediately said that I would. Andy gave me a copy of the paper and we started to look at it immediately.

It was clear—instantly—that the paper was from a professional mathematician, although, there were some oddities. For example, there were some standard results from complexity theory that Ed proved from scratch, rather than just cite them. This is usually a “red-flag” that the author is not well versed in theory, yet to me it did not rule out that there might be something important in his paper.

Andy and I decided that the paper was sufficiently sketchy that we would have to talk to Ed directly about the details. Andy called Ed and we setup a meeting that was to take place in the computer science building in two days. The goal of the meeting was simple: go over his proof section by section to figure out whether or not it was correct.

The Meeting

What started as a private meeting of Ed, Andy, and myself quickly snow-balled into a mini-conference. Somehow word got out that the problem had been solved. When we met with Ed we had to use a large classroom to hold the number of people who hoped to see history being made.

The meeting was “run” by Avi Wigderson, Andy, and myself. Of course Ed was there as an “oracle” that we could call on to ask questions about his proof. But, the plan was that we would try to go over the proof and only use Ed when we got stuck on a point.

Ed’s proof was based on a novel definition of a family of computations classes,

$\displaystyle {\cal C}_{1} \subseteq \dots \subseteq {\cal C}_{m} \subseteq \dots$

Each class really was defined by a restricted class of logical formulas. The base class ${{\cal C}_{1}}$ was very weak and had only simple operations like addition, multiplication, and equality. Then, each class ${{\cal C}_{i+1}}$ was the last class with a type of restricted quantifier added. Finally, he needed that each class was computable in linear time, and that each class had a certain technical property ${X}$ that was the key to his whole proof.

If all this worked, then he could prove a separation theorem, that would imply that P${\neq}$NP. This is a rough outline, as best we could figure out at the time.

The main structure was fine: the classes nested just as claimed, and if all was true the last step of proving P${\neq}$NP would follow. The base class ${{\cal C}_{1}}$ could be shown to have property ${X}$ by a nice argument.

The first rub, curiously, was the claim that the base class could be computed in linear time. Now multiplication is computable in nearly linear time, but Ed’s proof needed that the time was exactly linear. Nothing higher would work. Avi and Andy tried some different ideas at the board, and we asked Ed. He “forgot” how this step worked–we were stuck. This was scary that we were stuck at the first base case.

Then, I realized a trick. By a simple application of the Chinese Remainder Theorem (CRT) we could check that ${x \cdot y = z}$, which was all that was needed. This is when—I recall—Avi said that the CRT was the only theorem that I knew. He says that he never said this. But, in any event the CRT theorem did allow us to get past the first case—we were unstuck. The class ${{\cal C}_{1}}$ was indeed computable in linear time.

We then turned to the inductive step. It was here that we got stuck again, since we had been at the proof for a couple of hours we all agreed to adjourn for the weekend. We planned on getting together again the next Monday.

The Outcome

Since the meeting ended without any conclusion, we all left confused. We were starting to understand what Ed was trying to do, but we were all still confused. At least I was.

I decided that since it was a Friday I would try to spend the weekend either finding the bug or figuring out if the proof was correct. I sat down that Friday night and began to think about what was happening, when the phone rang. It was Michael Rabin calling from Harvard. Michael had heard the rumor, and tried to reach Avi to see what was up. Failing that he called me.

Michael said that he knew Ed Nelson well, and that Ed had done very solid research over the years in a variety of areas. Michael had not seen or even heard any details of the proof, but was excited that it might actually be correct. I told Michael that I was still trying to understand Ed’s ideas and I was still confused. We ended the conversation saying that I would get back to Rabin when I knew what was up.

In a few hours I figured out the problem. The proof of the first inductive step worked: the class ${{\cal C}_{2}}$ had the properties that Ed needed. But, the next step of the induction failed. Once the class became powerful enough his property ${X}$ no longer held. What had thrown Ed off and confused us was that the induction did not fail immediately. I re-checked my observations and soon I was sure that the proof was wrong, and moreover it could not be fixed.

I reached Avi who also by then had also found the error, and we then called Michael. The next week Andy and I spoke to Ed and explained why his proof could not work. He listened carefully, and after a few days of thinking acknowledged back to us that his proof did not work. Oh well. It would have been cool to see a solution.

I thought the proof was dead, the claim was withdrawn, and P=NP was back as a completely open problem. But, I was too premature.

The Proof Returns

A year later Anastasios Viglas and I proved a result about the complexity of SAT. A few days later I was visiting Telcordia for the day, and I told someone about Viglas’s nice theorem, which was to be a part of his thesis. They said that sounded interesting, but they had heard that Ed Nelson had resolved the whole question—he had proved P${\neq}$NP. I said I was aware of his earlier proof, but that had fallen apart. They said that they thought this was a whole new proof, and added the interesting detail that the math department had just had a big party to congratulate Ed on his work.

Viglas’s theorem would be wiped out if Ed was correct, his thesis would be setback, and in general it would be a problem. I had to find out what the true story was—was there any chance that Ed had actually fixed up his proof?I doubted it, but I needed to know. Since I was at Telcordia, I could not just run over and see my friends in theory or over at math. I had to try and reach people by phone or email.

Just my luck everyone was out that afternoon. No one answered the phone, my emails were not returned, and I had no luck finding out anything.

I finally got the scoop the next day, when I was back in Princeton. Ed’s party was a celebration for something else. He did not have any new proof, and so our small result was safe.

Open Problems

The usual problem is resolve P=NP. But, I think this episode raises some interesting questions. We spent a lot of time and energy debugging a proof that was wrong. Rumors started to fly—a few less doubts and things would have completely spiraled out of control. The New York Times would no doubt have been the next to jump in, if we had not found the serious bug in the inductive proof as quickly as we did.

How should we handle claimed proofs from professional serious researchers?

August 20, 2009 10:52 am

Superb article.

August 20, 2009 7:38 pm

How should we handle claimed proofs from professional serious researchers?

What happened in the Nelson case seems perfectly reasonable. The worst case scenario if things go wrong is a few mistaken news articles saying P has been shown not to equal NP, but those things happen from time to time. In 2006 Nature published a news story about a bogus claim to have settled the Clay problem about the Navier-Stokes equations (a much less serious attempt than Nelson’s). It was awkward and a little embarrassing for both Nature and the mathematician who made the claim, but there was no real harm done. If the New York Times published a premature article about a P vs. NP claim, I don’t think it would be much worse (and it wouldn’t be bad at all if they made the tentative nature of the claim clear). In fact, you could argue that there’s no such thing as bad publicity for theoretical computer science.

If enough people think the proof might be right, there’s no issue: it will get sorted out soon enough. The toughest issue is how to deal with proof attempts that aren’t crank work but that nobody considers promising enough to want to check carefully.

August 21, 2009 6:13 am

This was a very fun read!

It is nice to see you putting out interesting blog articles at a rate higher than the more “popular” complexity theory blogs. You stay in the point and provide articles of the highest substance!

Thank you.

August 21, 2009 9:31 am

Thanks for the kind comment.

I hope you like the mix of history, theorems, and future ideas.

rjlipton

4. August 21, 2009 3:28 pm

Comig to your question. Everybody can make mistakes, so it is possible that wrong proofs will be assumed true for a long time. As I wrote, this funny thing came to my mind. Scientists cited never published paper for many times: (http://blog.codalism.com/?p=773)

I am sure there are a lot more similar examples. Solution to the problem maybe crtically analyzing everything.

August 21, 2009 7:07 pm

Fixed the link-not sure what happen? Seems to be working now.

Your right about wrong proofs. At least one of the famous Hilbert problems was “solved” and then “unsolved” with a gap of many decades.

August 22, 2009 10:22 am

Curiously, you do not seem to answer the question that you raise in your heading. So what *will* happen when P≠NP is proved? Of the opposite, wikipedia say:

The question of whether P = NP [...] is one of the most important open questions in theoretical computer science because of the wide implications of a solution. If the answer is yes, many important problems can be shown to have more efficient solutions that are now used with reluctance because of unknown edge cases. These include various types of integer programming in operations research, many problems in logistics, protein structure prediction in biology, and the ability to find formal proofs of pure mathematics theorems.

So what if the answer is no? What are the practical ramifications of that? That’s what I thought this article would be about.

August 22, 2009 2:11 pm

Take a look at this

6. August 24, 2009 9:51 am

Not that i am even remotely that far into mathematics, but I’d add some fan-comments if you allow me:

I’d say the choice of computation classes as a basis seems well chosen, but to separate them by means of discrete technical property additions does not sound that good, because the adding of the last property needed would be of a similar difficulty range than the whole problem. The linear time restriction could need some more work. Why would it not work outside linear time?

I think that claimed proofs would always have to be peer-reviewed, broadcasted over the internet and digitally archiving all the thinking proccess.

This story reminds me in some part to the proving of Fermat’s last theorem by Andrew Wiles which you probably already know of:

Anyway, i am kind of glad that P=NP has not been proven yet. This world would be very boring if it was… I’d bet for inequality but please do not ask me why

September 3, 2009 4:30 am

How should we handle claimed proofs from professional serious researchers?

For major problems with such enormous subtlety as P?=NP, handle such proofs just like anyone else’s: assume they are wrong until the proof has been carefully checked and is found convincing. With professional researchers, one hopes at least that (unlike amateurs) they will understand and accept the error once it’s found and pointed out. That seemed to happen with Nelson but I remember a similar incident in the 1980′s by a Canadian mathematician whose name I won’t repeat here. First of all there was huge buzz around my CS dept. Some folks got copies of the preprint but wouldn’t show it to lowly students like me. The proof had a lot of math that no one in the department understood but they seemed to believe it anyway. Then someone from the math dept got hold of it and found the error in an evening. The author accepted the error but sent a fixed version, which of course also had an error, and this repeated way more times than anyone felt was reasonable and I fear that the guy still looks bad from it after all these years.

Thanks very much for describing Edward Nelson, though. I wasn’t familiar with his work but just spent a while surfing his web site, which is VERY interesting. He developed something called predicative arithmetic which is a bounded arithmetic theory, that led to Cook and Bellantoni developing “predicative recursion”. I don’t claim to have read any of this carefully or really understand it, but predicative recursion is apparently sort of like Peano arithmetic with a very restricted induction scheme, so that the functions definable with it turn out to be exactly the PTIME functions. Therefore you can recognize such functions syntactically, and even invent (along the lines of Turner’s “Total functional programming”) a “PTime programming language” in which ONLY Polynomial-time functions can be implemented. Letting imagination go wild, maybe you can do the same thing for NP, then show non-equivalence through some kind of cut-elimination scheme. Or better, show equivalence, so you end up showing P=NP and there is an O(nk) algorithm for SAT, but k is one of those inconceivably large numbers that come out of subjects like Ramsey theory…

Anyway, when I prove P!=NP (heh), I’m not even going to claim it’s a real result, I’m going to completely formalize the proof in Coq or Isabelle before even telling anyone about it. Then I’ll post it here or in some other CS blog saying I have a pseudo-proof that’s sure to be wrong just like all the others, only I can’t find the error and would someone be kind enough to point it out for me, and if it turns out to be right, be pleasantly surprised. I think that’s about the only un-presumptious way for anyone to present a P vs NP proof these days.

September 3, 2009 4:32 am

Ehh, wordpress didn’t show my superscript in O(n**k). Kind of changes the meaning…

9. November 26, 2009 2:48 am

I wish more blog posts about mathematics/theoretical computing science were like this. It sounds much more exciting than anything I’ve heard in undergrad courses!

10. November 26, 2009 12:57 pm

“In a few hours I figured out the problem. The proof of the first inductive step worked: the class had the properties that Ed needed. But, the next step of the induction failed. Once the class became powerful enough his property no longer held.”

My question is about the inductive proof attemp. Can we say that if an inductive proof attempt fails for some reason and tested several times, should we give up any new inductive proof attempt?

11. November 27, 2009 8:59 pm

This is very analogus to “Are there finite primes?”. And no, it cant because p=N+1 cant divide 1.