What Will Happen When P≠NP Is Proved?
A story of the rise and fall of a serious attempt at a proof that PNP
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 PNP, 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 PNP. 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.
One day, at Princeton, Andy Yao grabbed me and told me that Ed Nelson had a draft of a proof that PNP. 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.
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,
Each class really was defined by a restricted class of logical formulas. The base class was very weak and had only simple operations like addition, multiplication, and equality. Then, each class 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 that was the key to his whole proof.
If all this worked, then he could prove a separation theorem, that would imply that PNP. 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 PNP would follow. The base class could be shown to have property 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 , 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 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.
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 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. 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 PNP. 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.
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?