Proofs, Proofs, Who Needs Proofs?
Why prove statements we seem to be sure are true?
Michael Atiyah, actually Sir Michael Atiyah, is one of the great mathematicians in the world. He has received awards from the Fields Medal, to the Abel Prize, for his seminal work in many aspects of algebraic geometry, topology, and operator theory. Besides his deep and beautiful results he has some striking insights into the nature of proof. For example, one of his quotes is:
I think it is said that Gauss had ten different proofs for the law of quadratic reciprocity. Any good theorem should have several proofs, the more the better. For two reasons: usually, different proofs have different strengths and weaknesses, and they generalise in different directions—they are not just repetitions of each other.
Today I want to talk about the P=NP question, and not even mention the claimed proof. Oh, I guess I just did mention the proof, but let’s agree to not count it, if that is okay.
I have recently spoken to a number of reporters, as you might expect Some were from the on-line media and some from the print media. Both types of reporters asked good questions and in general we had an interesting discussion. But one or two asked a question that I really had trouble answering. The question was not an obvious ones like: what is polynomial time, or what is NP. The question was:
Why is proving PNP an important result?
The trouble I had is simple: if most believe that PNP is true—perhaps obviously true—then why care if it gets proved? Yes, it is a famous problem, with a large monetary prize. No doubt whoever first proves the result will be showered with many awards and honors. But, still why the huge interest in proving something that we know is correct?
I have thought about this quite a bit and have some insights that I would like to share with you about their question. I wonder if you have other thoughts.
Does Any Proof Matter?
So why do we really care if there is suddenly a proof that PNP? As many of you know I am less sure than most that PNP. So perhaps the answer for me is it would be important because I have great doubts about it. But, I have already discussed a number of times and in different ways why I am skeptical about the conventional wisdom.
I can think of several different reasons why a proof of PNP would potentially really matter. The first has to do with the nature of proofs in mathematics. Let me explain.
I had the honor of meeting Atiyah a few years ago, and we had a chance to talk about the nature of proofs. One story he told me in private was quite telling. He told me that he had, many years earlier, proved a technical theorem about finite groups. He felt very sure the proof was correct, but sometimes late at night he would lie awake with some doubts. The proof was not a high level proof, it relied on a detailed analysis of the group structure. Since the proof was so technical and filled with case analysis he never felt that he really knew why the theorem was true.
Years later he found the proof. He realized that his theorem was true for a much larger class of groups than finite: it was true for compact algebraic groups. Further, the proof there was high level, was clear to an expert, and relied on no magic calculation, nor any case analysis. He said now he knew the original theorem was correct and he could sleep better at night.
He further said that the role of proof, in his opinion, is to not to “check-off” that a statement is correct. The role is to give insight into why the statement is correct. As you might imagine he was not very interested in machine proofs—at the time we discussed Thomas Hales’ proof of the Johannes Kepler Conjecture. While he understood the potential need for such computer-proofs, he really wanted to know why it was true.
Does A Proof Of PNP Matter?
Yes it does. Here are my three foremost reasons to think that such a proof could be very important.
A Proof Would Tell Why: Even those who are sure that PNP would like to know why this is so. This is exactly Atiyah’s point. A proof would give us insight into why there can be no efficient search for SAT.
A Proof Could Give Us New Methods: Perhaps the best reason is the hope that a proof that PNP would have to use new tools in the proof. These tools would hopefully shed light on computation in general. They could yield insights into the fundamental nature of computation. This is the best reason, in my opinion, for wanting a proof.
There are many examples in mathematics where this is exactly what has happened. The proof of a great result has many times created new tools and techniques that have raised the curtain and allowed us to see for the first time new insights into other problems. Certainly this would be wonderful if this were the case with a proof of PNP.
For example, Andrew Wiles’ proof of Fermat’s Last Theorem and Grigori Perelman’s proof of Poincaré have changed their respective fields. Wiles proof of Fermat has led to other fundamental advances in number theory, well beyond solving the one famous family of Diophantine equations. However, not all mathematical proofs of great conjectures use new techniques. There have been many solutions of long-standing open problems that used no new techniques. These were often very clever results, but the provers did not need new methods and tools. They were able to resolve the conjecture using well known methods—their proofs may have been very clever, but they did not change the landscape.
I have no idea how often the latter happens, but it does happen. Some friends who are experts on the Riemann Hypothesis once told me their greatest fear is: what if someone came along with a clever proof, but one that “just” used known technology in a clever way. They would then know that the Riemann is true, yet they would be quite disappointed.
Hopefully, this will not happen with PNP. Hopefully.
A Proof Helps With Goals of Security: Modern cryptography uses the term provable security. In many cases this means only that they have proved that breaking their system implies that some hardness assumption, such as on factoring, is wrong. Even a proof that PNP would not rule out that such assumptions are false: recall that factoring is not known to be NP-complete. I think, however, that a proof of at least PNP would be of some comfort to cryptographers. Their special hardness assumptions might still be unproved, but a proof would move us closer to perhaps one day really having provable security.
Are these good reasons? What are your reasons?
Okay I will comment on the state of the claimed proof—actually these are comments from Ken Regan, but I support all he says.
These and other reasons have been reflected in the community-wide discussion taking place here and in other blogs. The recent CACM post substituted “” for “PNP” partly to symbolize that PNP is a front-end for a set of deeper beliefs about computation. This point was made eloquently by Ryan Williams in a comment here.
As noted yesterday in comments here and elsewhere, Vinay Deolalikar has removed all previous manuscripts except the 3-page synopsis from his public webspace at HP Labs. His main page has the statement:
“The preliminary version was meant to solicit feedback from a few researchers as is customarily done. It illustrated the interplay of principles from various areas, which was the major effort in constructing the proof. I have fixed all the issues that were raised about the preliminary version in a revised manuscript (126 pages); clarified some concepts; and obtained simpler proofs of several claims. This revised manuscript has been sent to a small number of researchers. I will send the manuscript to journal review this week. Once I hear back from the journal as part of due process, I will put up the final version on this website.”
The passage of time and recent coverage may be obscuring the fact that privacy was Dr. Deolalikar’s original wish—and that he was “outed” by a sequence of forwarded e-mails “a couple of steps removed” (original source). We feel that any effort to draw conclusions beyond the fact that his previous releases needing fixing, and to declare what his further actions should be, should be tempered by this realization. We have expressed disappointment at the lack of response beyond the synopsis, but what he is doing now is in line with his original intent.