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 P${\neq}$NP an important result?

The trouble I had is simple: if most believe that P${\neq}$NP 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 P${\neq}$NP? As many of you know I am less sure than most that P${\neq}$NP. 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 P${\neq}$NP 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 P${\neq}$NP Matter?

Yes it does. Here are my three foremost reasons to think that such a proof could be very important.

${\bullet}$ A Proof Would Tell Why: Even those who are sure that P${\neq}$NP 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.

${\bullet}$ A Proof Could Give Us New Methods: Perhaps the best reason is the hope that a proof that P${\neq}$NP 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 P${\neq}$NP.

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 P${\neq}$NP. Hopefully.

${\bullet}$ 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 P${\neq}$NP 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 P${\neq}$NP 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.

Open Problems

Are these good reasons? What are your reasons?

$\displaystyle \S$

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 “${Q}$” for “P${\neq}$NP” partly to symbolize that P${\neq}$NP 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.

1. August 18, 2010 1:26 pm

There is another great reason why a proof, or disproof for P=NP is important. If P != NP, then there is a definite bound on how tightly we can optimize various algorithms.

With Moore’s law seemingly coming to end soon, we can’t always rely on bigger faster machines to deal with harder problems. I’ve always suspected (or at least held out hope) that there is a previously undiscovered class of algorithms that would provide us with reasonably performing programs to compute some of these harder problems. SAT is not all that interesting from an application’s standpoint, but there are certainly complex database designs that are unachievable right now due to poor performance. Any real growth in data would crush the database performance beyond usability. If better performing algorithms existed, we could build a whole new class of software that hopefully would harness the full power of our machines. If not, then would would have to look to other alternatives.

Paul.

August 18, 2010 8:13 pm

I must disagree on one point: SAT in fact has a wide variety of practical applications. Just this week I’ve been working on hypergraph partitioning, which is useful for numerical linear algebra; VLSI design; automated theorem-proving of design requirements (see Dan Jackson’s “Alloy” project at MIT); partitioning subtasks among parallel processors; etc. There is high demand for better, faster SAT solvers.

December 8, 2013 1:43 am

I wish to inform you about a claim of proof that P=NP, subset sum problem solved. I saw this at http://www.fofallthings.com. Regards.

August 18, 2010 1:44 pm

Hi,
wouldn’t you say that the third option, independence, for P!=NP is a looming danger that would be resolved by proving it?
Independence would cast massive doubts on the Church-Turing Hypothesis since one can certainly write a real implementation of SAT that runs in polynomial time or one can not.
The implications for logic and associated theories would be profound: ZFC would have been shown to be insufficiently strong.

• August 18, 2010 6:00 pm

I find the fact that people continue to say “Church-Turing thesis,” instead of, say, “Dershowitz-Gurevich Theorem” strong evidence that logicians never talk to theoretical computer scientists, and researchers in formal methods never talk to researchers in complexity theory. What excited me most about the past week on this blog is that everyone was talking with everyone, regardless of their academic culture.

Dershowitz and Gurevich axiomatized the notion of “effectively calculable” using abstract state machines, and proved both Church’s thesis (all effectively calculable (partial) functions are general recursive) and Turing’s thesis (the effectively calculable functions are exactly those which can be programmed on a Turing machine). Bulletin of Symbolic Logic, 2008. I don’t understand why this paper isn’t famous.

http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.146.5402

August 18, 2010 6:43 pm

Umm, but the Church-Turing thesis is a thesis, not a conjecture. It relies on informal view of computation and claims that certain formal models of computation capture it. So how could it ever be proved? It could be disproved – by showing that something that everybody agreed to be a natural form of calculation was not computable by a Turing machine.

August 19, 2010 2:54 am

It’s not famous because it only proves that the thesis falls out as a consequence of natural axioms. This is not in doubt.

August 19, 2010 7:33 am

A problem with this ‘proof’ is that the notion of Abstract State Machine axiomatises a very sequential notion of computation. But there’s no reason to believe that all computation should be sequential. Abstract State Machines don’t express concurrency in a convincing form.

August 20, 2010 1:48 am

@Gent: You cannot dispute the fact that a thesis can be formalized in a natural system, and derived from some natural axioms. Such a proof shows that the thesis is not implausible, and the bare minimum axioms that the thesis requires hold. This can be insightful. But I don’t see why, as Aaron above insists, this should be cause for fame. Elegant, nice, expository—yes, but not ground-breaking.

August 19, 2010 6:01 am

I don’t understand how this is related to Church-Turing thesis. Say there was an algorithm for SAT which:
a) runs in polynomial time for all inputs and
b) fact a) would be impossible to prove for this algorithm (and for any other polynomial time algorithm solving SAT). Why would the Church-Turing thesis be violated here?

I am pretty sure there are plenty of natural problems independent of ZFC. If it is possible to prove the independence of some of them, it tells more about the strength of logic than about the weakness of ZFC in my mind.

August 19, 2010 8:18 am

tuomas,
you are right, independence would not violate church-turing (i did not write that).
but still: the intuition (at least mine) is that the correspondence between the complexity classes as formulated by turing machines do exactly correspond to the real toughness to tackle a problem in principle with a real computer (log is very easy and exp is way too hard). i am sure most people would share that sentiment.
and to me church-turing is the name of this belief, that real computation and the mathematical model are almost isomorphic in nature. i know it does not say that and i should have been clearer.

there are quite a few problems known to be independent of ZFC, some even are about subsets of natural numbers (Ramsey-style). But all of them involve quite complicated maths and do not really “harm” or even concern anyone outside set theory so far.
To show that one of the biggest and most prominent problems of our times is independent and whose instances of instances can run on factual computers would shock a lot of people and there would be demands to strengthen ZFC, don’t you think?

August 21, 2010 8:36 am

Ok, I never thought about Church-Turing that way.

The thought about demands of strenghtening ZFC in case that P=NP turned out to be independent is very interesting. In the case of CH it might be conceivable to just add some weird axiom which implies not CH, but I really doubt it would be possible to find a new axiom which would prove P neq NP and gain general acceptance. Seems like the finitary human reasoning is already pretty well captured in ZF.

Then again, wouldn’t it be funny if choice implied P neq NP and the question would be independent of ZF? 🙂

August 21, 2010 9:16 am

Hm, but what if there is only a partial independence theorem? Say if it is eventually proved that if P != NP, then this is unprovable in ZFC. I guess then one could technically add P = NP as an axiom, but this would be rather unsatisfactory if it is not “really” true, since there would be no useful algorithm. Adding P != NP instead would risk introducing an inconsistency.

August 18, 2010 1:46 pm

I have to say I’m surprised by the pragmatism of the discussion of the value of proofs. Proofs are important because they establish firm stepping stones independent of whether the form of proof is otherwise illuminating.

There are quite a few theorems conditioned on the truth of P!=NP, Riemann, and others but those conditioned results are rarely taken as lemmas for deeper analysis because nobody is comfortable treading too far out on ice of uncertain thickness.

August 18, 2010 2:51 pm

I find the list very insightful. From an email correspondence a few days ago (names removed):

“A proof of P!=NP would (unfortunately) fail to alter the world at all, except for the few individuals who dedicate a significant portion of their time to complexity analysis. We all generally operate under the assumption that P!=NP, there’s not a lot of effort going into trying to find polynomial solutions to NP complete problems.

Ah, now a proof that P=NP. That would be quite something. If only… THAT would change the world.”

To which I responded:

“This is often forgotten…

Theorems aren’t only important for their direct, causal implications/results. Theorems are important in and of themselves for their approach, their perspective, and their creative observations. It’s likely that a proof that separates P from NP will blast open entire new worlds of investigation. The techniques used to separate the classes are bound to be very powerful and aptly applicable to many other open problems (perhaps even outside the complexity world?).

A proof that proves P != NP would truly change the world in some seriously awesome ways.”

But I think you said it much more succinctly: “A Proof Would Tell Why”

August 18, 2010 2:57 pm

There’s a minor variant on your stated points: the understanding of P vs NP is in the context of a stronger Church-Turing hypothesis about actual computational mechanisms having identical sets of complexity classes. A proof of P != NP may highlight some conditions on computational mechanisms which are crucial to the difference, which may be a guide for searching for physical effects which violate them. That’s a real, real long-shot but it’s conceivable.

6. August 18, 2010 4:47 pm

Is it likely that a proof for P!=NP would result in more efficient algorithms as a result of greater insight into computation?

August 19, 2010 12:40 pm

Amir: This is actually plausible.

In fact we know that a proof that BPP != EXP (separating randomized polynomial time with two-sided error from exponential time) does imply better deterministic algorithms for BPP on almost all instances! See Impagliazzo and Wigderson’s “Randomness vs. Time: De-randomization under a uniform assumption”. To carry the analogy over, perhaps P != NP would lead to better algorithms for problems in P, in some sense.

August 18, 2010 6:49 pm

A correct proof of P!=NP does not rule out P=NP. It maybe followed by another correct proof of P=NP. Two proofs of “P=NP iff P!=NP” were presented in the previous blog topic that no one can ever falsify.

• August 18, 2010 7:20 pm

Dear Rafee Kamouna,

Yes, we read your proof, I kindly request you not comment same thing again and again.

Thanks

August 19, 2010 11:31 pm

You are the first to say you read them.

August 19, 2010 2:56 am

August 19, 2010 11:33 pm

It is well-known that math can be contradictory.

August 19, 2010 1:11 pm

You can claim \$2 million from Clay then as you concisely and rigorously show both that P = NP and P≠NP. Clay can afford it, they need to dispose off the Poincare \$1 million anyhoo…

August 18, 2010 7:14 pm

When almost everybody believed that the sun moves round the earth (and mind it – the believers must have considered themselves rational enough in their own way) – the ‘shocking’ news came otherwise.

Everyone believed there’s aether. It was disproved.

Everyone thought light is wave. photo-electricity was explained, quantum mechanics was born.

If we think of mathematics, computer science, as part of the bigger scheme of fundamental sciences – the overall pursuit for unraveling abstract as well physical truths – who knows we won’t get surprised again just the same way? By the answer to P/NP question.

We owe this to our posterity.

August 19, 2010 1:08 am

Anonymous,
It is very refreshing to see a comment like that. In one of my comments I asked the readers if “D”‘s proof were about P==NP, would it have got as much response. No one answered.

On “Shtetl-Optimized” I posed the same question.
One reader disguised as “C” compared my hypothetical question to “What if pigs could fly”.
(And I have a good guess who that is)
Clearly, the discovery of new theories have always been at the mercy of those in “power”.

I have my own story of the personal experience and humiliation on a “#P=FP” proof that I am having hard time to find a reader. May be I should post that to point to the prevailing arrogance and ignorance in the community.

August 19, 2010 10:56 pm

Check out the P versus NP poll http://www.cs.umd.edu/~gasarch/papers/poll.pdf

2.2 How Will it Be Resolved?
1. 61 thought P6=NP.
2. 9 thought P=NP.
3. 4 thought that it is independent. While no particular axiom system was mentioned, I assume
they think it is independent of ZFC.
4. 3 just stated that it is NOT independent of Primitive Recursive Arithmetic.
5. 1 said it would depend on the model.
6. 22 offered no opinion.

Stephen Cook selected Vinay’s proof based on resume, not P==NP or P !=NP convictions.

August 19, 2010 11:59 pm

#P = FP? Why don’t you implement the algorithm?

August 18, 2010 7:18 pm

This is vaguely reminiscent of the discussion regarding the proof of the 4-colour theorem on planar graph colouring in the 1970s.

At the time, the proof was controversial because it essentially used a computer to show that a minimal counterexample to the (then) conjecture could not exist.

But really the objections to the “computer” part of it were spurious – people were mostly unhappy because the proof did not show WHY a planar graph could be coloured with just 4 colours, and I think just latched on to the then-unprecedented use of computers to hang their complaints on.

Subsequently, the computational portion of the proof has been checked, double-checked and substantially simplified but the proof structure remains the same – a planar graph is 4-colourable simply because it is impossible for a planar graph to require 5 colours.

Personally I don’t have a problem with this – it is just a straightforward (though lengthy) proof by contradiction.

August 18, 2010 7:26 pm

I think that the difference between ‘what’ we believe to be true and ‘why’ and the importance of the latter is not restricted to mathematical questions. Examples from other sciences may also help when discussing the issue.

There are several things about the physical world we may believe to be true (The What).
– A stone that is thrown up will fall down.
– A potato slice placed in very salty water will wilt.
– If a current is passed through two parallel wires, they will attract or repel each other.

Volta and Galvani knew that if they placed a frog’s leg between two metal plates, they could detect a current. This is a fascinating observation but in itself is a piece of trivia. Asking “Why?”, on the other hand leads us to the theory of electromagnetism, whose impact can only be grossly understated in my limited vocabulary. Try imagining a world without lights. In general,
we believe certain things are true because we repeatedly arrive at the same observation. Observations (The What) are interesting but convincing explanations for the phenomenon (The Why) are more interesting. The world is a profoundly different place because we know something about gravitation, osmosis and electromagnetism.

I think that much of this applies to mathematical statements and their proofs. Sure, not all proofs bring great insights and advances. The same is true of natural sciences. We could ask what causes the image seen when a spotlight is shone on a necklace of glass beads or how Walter Levin got this picture. In both cases the answer follows from what we know and understand about the world. At other times, dramatically new concepts are required to provide an explanation and we have the privilege of another glimpse into the intricate structure of the universe (mathematical or physical).

11. August 18, 2010 9:50 pm

I think one must also consider the human desire to do something fulfilling.

A proof can be considered a work of “intellectual artistry”, and one may be driven to do it just as an artist is driven to write a great novel, paint a great painting, etc.

We pay people to do sometimes purely theoretical research which may not have any applications in the near future. And some love to do it.

Well-regarded scientists have been in love with what they do. To realize one’s potential in one’s work, no matter whether it has near-term applications, to create something great and beautiful, is one of the greatest traits of human beings.

And I suggest that the best works in science, as in art, are those which the person was not strictly required to do as part of his job, but did it because that was, to put it simply, what he was born to do.

August 19, 2010 12:05 am

I admire the overall constructive tone of the discussion of Vinay D’s purported proof but I am dismayed by the increasingly accusatory tone.

I agree that Vinay should have written his manuscript formally as a logical progression of lemmas and theorems but in fairness to him, he sent his write-up to a small number of people. One of them could have gently asked him to rewrite before sharing with others. Instead it got widely distributed and received an amount of public scrutiny that he may not have intended.

For those suggesting that he should have shown his manuscript to a colleague, pl remember that HP labs does not have the strongest theory group. I remind everyone of Prof Lipton’s comment that people should be encouraged to work on hard problems and for many outsiders the only way to receive suggestion is to email to a small group of top researchers.

We need to step back and give Vinay a chance to work on his ideas. He should not be discouraged from submitting to a journal. A reasonable editor, I hope, will ask likes of Tao, Immerman, Wigderson, Sipser, or Karp to referee this paper and they will have a chance to judge the soundness of Vinay’s revised results.

Finally speculating whether or not he got his ’15 minutes of fame’ is plane nasty.

August 19, 2010 12:14 pm

I couldn’t agree more. I have a CS researcher friend who works with VD at HP. Yesterday, he, in essence, told me the same about VD’s intentions. Certain posters here (especially one monikered vloodin) have attacked VD’s integrity and character in harsh and sarcastic language (calling him a “quack” !). That is entirely unwarranted. From vloodin’s voluminous “show-off” discourses here, I am also assuming that, in the foreseeable future, (a) he will conclusively prove P !=NP – hopefully with help from Dr Tao, or (b) conclusively demonstrate that is it impossible to prove or disprove that P ! = NP.

August 20, 2010 6:02 am

Terence Tao and vloodin were valuable contributors. Your non-technical side comments are interesting.

August 19, 2010 12:43 am

I find it mildly disconcerting that a very respected academic like Prof. Lipton would have trouble answering a question that amounts to “why does your professional activity matter at all?” Perhaps Prof. Lipton has expressed himself unclearly; I have trouble believing that a senior, productive researcher like himself has only just begun contemplating whether what he does is worthwhile.

The reason I am posting this at all, instead of going with the lack-of-clarity hypothesis, is that in grad school sometimes it feels as though nobody cares whether what they do is any good in the bigger scheme of things. Sometimes it seems that people only care about proving the next result.

• August 19, 2010 1:54 pm

El Duderino: “In grad school sometimes it feels as though nobody cares whether what they do is any good in the bigger scheme of things. Sometimes it seems that people only care about proving the next result.”

Elan Lindenstrauss—one of today’s ICM Field Medalists—is a graduate Israel Defense Force (IDF) Talpiot Program (at present Lindenstraussis is an IDF reserve major).

Talpiot is a defense-oriented STEM program which one graduate has memorably said: “You learn self-confidence, not to be afraid of anything. No subject is too complex to go after, and no answer should be taken for granted.”

Many folks (perhaps most) would agree that this describes a nearly ideal STEM education—there are no reports (AFAIK) of Talpiot graduates who feel as isolated as Duderino does—and so perhaps the Talpiot Program will be receiving increased attention for this reason.

These are matters that arouse deep passions, and engage the most complex of human issues, and so I hope all who post put their best foot forward … I speak as the father of a Marine who has just returned home from his fifth combat tour.

14. August 19, 2010 1:54 am

“A proof would tell us why”: That is a beautiful phrase.

August 19, 2010 2:59 am

I am surprised that this phrase is such a revelation to the TCS community! One would think it was obvious. Isn’t that how proofs are introduced in high school? Isn’t that how experiments are introduced in high school physics? Or perhaps you are saying that we now understand this phrase after having come full circle?

August 19, 2010 1:12 pm

Well, the usual formalization of proof does not seem to support the “why”, at least not in the sense we are talking about. The definition of NP does not, it just cares whether there is a short proof for the candidate theorem in hand. But many good proofs in real life convey much more than just the fact that the theorem is true, they usually lead to lots of nice corollaries and generalizations.

I would say that many proofs I did in high school were not satisfactory. They effectively answered the question “why” by saying “because the first line is an axiom, the last line is the theorem, and all the little pedantic steps in the middle are valid”.

Understanding this disconnect is an interesting problem but it’s very hard to figure out how to get started. How do we formalize the case when the proof verifier finally “knows why”?

August 20, 2010 1:20 am

In high school, we were taught that our written proofs correspond directly to our level of understanding, and so if our proof was not as clear as it could ever be, we would not get credit. So, our proofs would have three columns with little explanatory notes in the third column, “derivations” in the middle column, and numbers or other annotation in the first. We would get prizes for best exposited proof. So by high school graduation, it appeared to me clearly that the function of proof was to clarify, rather than prove. In fact, my impression was oddly stretched in the other direction: I almost came to believe that a theorem was usually easily known to be true … that was not the hard part. The hard part was to write a proof that unveiled all the hidden reasons. Of course, later I realized that this extreme of a view is also flawed.

It is in this context that I wrote the above comment. So it is no surprise now, that I am surprised that others don’t see it this way.

16. August 19, 2010 3:00 am

Why prove statements we seem to be sure are true?

Indeed, all mathematicians fall to this trap in the most blatant way:

How do you know that two proofs are about the same theorem?

This occurs even in very simple cases like the Pythagorean Theorem, it is so obvious that we “know” these proofs are about the “same theorem” that any question about showing evidence of this match is swept under the rug in favor of nitpickings about the technical details, the “cleverness” and “elegance” of the methods and the “deep philosophical” implications of this or that proof.

Hold on guys, instead of wallowing in your addiction to the “joys of mathematics” look at what is hidden in plain sight and you are completely missing, it is probably the key to the higher results you are longing for.

17. August 19, 2010 4:55 am

The security section seems a bit iffy to me. Integer factorization not being NP-complete isn’t really the issue. A P != NP proof wouldn’t validate the hardness assumptions even if it were NP-complete, because cryptographic hardness is closer to a best-case notion than a worst-case notion. Imagine using randomly generated SAT problems as the basis for a cryptosystem, for example! The provable hardness buys you nothing, because of the fatal prevalence of easy instances. Perhaps NP-completeness theory can be extended in the direction of covering cryptographic hardness, but that was the hope Diffie & Hellman expressed in 1976, and it hasn’t come close to happening yet. So I think I’d side more with Christos Papadimitriou’s retrospective statement that NP-completeness is essentially irrelevant in this area.

August 19, 2010 1:12 pm

I think integer factorization not being NP-complete is definitely an issue. And the (still open) absence of a reduction from factorization to the RSA problem is probably even more so. Another fact that makes one nervous is that almost all current cryptosystems are based on such problems (factorization, discrete log, shortest lattice vector, etc.) that are in fact in NP \cap co-NP. The history of the last few decades has made this class particularly notorious in the sense that several problems here tend to fall down into P (or BPP) eventually, PRIMES being a case in point.

The point about cryptography requiring average case hardness and not just worst case is well taken, but it’s wrong to think that using any two large randomly generated primes p and q and then using their product as the basis for an (RSA) cryptosystem is somehow necessarily better than “using a randomly generated SAT problem as the basis for a cryptosystem”. There are vastly many easy instances in the former case as well (p and q may not be “close together”, p-1 and q-1 must not be smooth, etc.) and that explains why most implementations generate and test for Sophie-Germain primes (to construct “safe primes”). So in some sense, our greater insight into these number-theoretic problems (that makes them “easier” than NP-complete problems) also actually helps us generate “good” instances that are hard in the average case, thereby making them more suitable for public key cryptography!

But I wouldn’t call NP-completeness “irrelevant” for cryptography, although, sure, almost all of modern cryptography is based upon layers after layers of additional assumptions (existence of OWFs, existence of trapdoor OWFs, etc.) on top of the P \neq NP one.

August 19, 2010 5:10 am

>Modern cryptography uses the term provable security.

modern “marketing” uses a lot of buzzwordish terms, prabably all of them wrong on purpose. check the small print in both cases.

August 19, 2010 5:12 am

I recently got into an argument with someone (a EE systems guy) when I said that P v/s NP is the hardest problem in all of CS. His contention was that this is what theory people like to claim (i.e. everyone thinks their problems are hard) and that there must be other problems in CS that are as hard or harder (e.g. achieving true AI). I gave up on the argument after realizing that there is no easy way to quantify the hardness of solving a problem (may be “number of man years”?).

Do folks think that P v/s NP is the hardest/most important/ problem in CS? Or do you think it is a meaningless/silly question? Why or why not? What would, for example, be the top 5 problems in CS in terms of impact?

August 20, 2010 2:02 am

I think P vs NP the most interesting question in computer science.
If archieving true AI is harder than solving P vs NP i don’t know.
It might be an advantage that in case of P vs NP atleast the question is well understood.

• August 20, 2010 3:56 am

If archieving true AI is harder than solving P vs NP i don’t know.

Relax, nobody knows, up to now the “question” is not understood at all.
Before “achieving” anything one would have to know what intelligence IS.
Even famous AI researchers are driven to crankiness by this elusive problem.

20. August 19, 2010 5:20 am

“A Proof Would Tell Why: Even those who are sure that P NP 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.”

Yes, indeed; and the formal definition of the class P may be a contributing factor in blocking such insight.

Foundationally, number-theoretic functions and relations over an infinite domain D ought to be viewed as computational instructions (which may, or may not, be uniform) that, for any given sequence of allowable values to the variables in the function/relation, determine how the function/relation is to be evaluated—and whether, or not, the result of such evaluation yields a value (or values)—in the domain D.

They ought not to assume—as in Cantorian set theories—that the evaluations always determine a completed infinity (set) that can be referred to as a unique mathematical constant which identifies the function/relation in a mathematical language (or its interpretation) outside of the set theory in which the function/relation is defined.

However, the formal definition of the class P by Stephen Cook admits a number-theoretic function F of a computational theory—viewed set-theoretically as extensionally defining (and being defined by) a unique subset L (treated now as a completed infinity in computational theory) of the set Sigma* of finite strings over some non-empty finite alphabet set Sigma—in P if, and only if, some deterministic Turing machine TM accepts L and runs in polynomial time.

The delinking of the manner in which the language L is arrived at, from the function that defines it, immediately blocks any possible insight into the ‘why’ of further argumentation.

Let me illustrate by defining P as the class of number-theoretic functions that are (algorithmically) computable by a deterministic Turing machine TM in polynomial time and which are, ipso facto, effectively verifiable.

Consider now the classes of number-theoretic functions that are:

(a) computable by a deterministic Turing machine TM and effectively verifiable;

(b) not computable by a deterministic Turing machine TM but effectively verifiable.

The natural (and perhaps common) approach suggested by Cook’s definition for showing that P=/=NP would be to restrict one’s search to seeking a number-theoretic function that is in the class defined by (a), but not in P.

(See for instance Step 4 in Lance Fortnow’s blog: http://blog.computationalcomplexity.org/2009/01/so-you-think-you-settled-p-verus-np.html)

However, this presumes that a problem such as SAT, or the travelling salesman problem, can be formally expressed by a number-theoretic function that is computable by a deterministic Turing machine TM.

It is this presumption that may be blocking any insight into a resolution of the PvNP problem.

Now we can show (link below) as trivial corollaries of deep, and beautiful, classical theorems—arising out of Goedel’s Theorem VII of his seminal 1931 paper on formally undecidable arithmetical propositions; Turing’s analysis of computable numbers in his seminal 1936 paper; and Tarski’s definitions of the satisfiability and truth of the formulas of a formal language under an interpretation in his seminal 1933 paper, which together suggest how we may link Turing-computability and first-order PA-provability—that there are number-theoretic functions which are effectively verifiable, but not computable by a deterministic Turing machine.

So, if we admit the possibility that the travelling salesman problem may be formalisable by a number-theoretic function that is effectively verifiable, but not computable by a deterministic Turing machine, then we not only have that P=/NP trivially, but we can also ‘see’ why it is trivially so!

21. August 19, 2010 6:23 am

The security issue is mentioned and indeed there are many cryptographic protocols that rely on a supposedly difficult problem that is not yet proved like factoring integers or “not P=NP”.

For instance the McEliece cryptosystem and several other code based public key cryptosystems rely on the hardness of decoding error-correcting codes. The associated decision problem is proven to be NP complete.

Now what happens if the problem is not difficult and someone or some institute (secret agency) of (criminal) organization has an efficient algorithm that solves the problem but does not make this public? That would give them a way to intrude a system while everyone else considers it secure because it is based on that “difficult” problem!

August 19, 2010 7:09 am

Ruud,

That is not exactly right. Any public key system is NP intersect co-NP and therefore is not NP-complete—unless some surprises happen. So even if P is not NP does not help crypto. Even worse is what if NP could be done in near polynomial time, that would also be a problem.

• August 20, 2010 8:17 am

Dick,

I want to understand your remark “Any public key system is NP intersect co-NP and therefore is not NP-complete….” correctly. Do you mean by “Any public key system” all those systems or all those that you know? Could you give an explanation in the first case?

I like your site very much.

August 19, 2010 7:22 am

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.

Why can’t a clever proof that uses known methods change the landscape of a field?
I don’t have any examples to show this has happened in the past, but it could be possible.

August 19, 2010 7:29 am

There are lots of examples where clever proofs did not add to the knowledge, since they did not add new tools.

August 21, 2010 12:21 am

Who will be willing to read to the proof if it is not supported by the beliefs of the majority?

I submitted a paper on #P=FP to TOC (an online journal). The chief editor László Babai, said no one is willing to read your paper!
It has been two years now– not a word since then!

August 21, 2010 2:13 am

Gr8 Question, Javaid!

August 19, 2010 7:25 am

A comment on machine proofs like the 4-color theorem. I think the issue is still there whether or not we really understand the 4-color theorem. Back to my quote in the post: why else would Gauss want so many different proofs of QR theorem. He wanted to really understand the magical theorem that relates the quadratic structure modulo two primes.

• August 19, 2010 8:17 pm

Would you include non-machine proofs that are extremely lengthy and complex, such that no more than, say, the author and one or two people understand them? It’s not identical to the machine-checked proof issue, but it still seems that when the answer to the “why?” is “because of this 200-page monograph that 3 people in the world understand”, one might say that the answer isn’t that much more satisfactory than if it were, “because of this 200-page case analysis verified by a machine”— unless, in either case, some more succinct kernel of truth can be extracted.

• December 14, 2010 12:17 pm

Usually you can summarize a long paper pretty succinctly using heuristics. By doing that you can express and communicate the main ideas of the paper and explain the ´why´ of a theorem, without going into various details (that may take up a significant portion of the original paper). But this can’t be done as well with a machine proof (usually), because if the whole ‘idea’ is to check 10^14 cases (which may very well be hard to accomplish), then there’s not much to understand.

• December 14, 2010 3:01 pm

@Woett
You are right, this is because machine proofs have no structure, they use brute force over a handful of finely tuned “tricks”.
However machine proofs could be structured, this would require a hierarchy of “meta-strategies” on the proof elaboration likely akin to human heuristics.
But the Automated Theorem Proving hackers have no interest in anything which does not gives an immediate payoff and the gifted mathematicians are not interested in Automated Theorem Proving nor do they have insights into their own unconscious process, therefore we are stymied in a dead end.

August 19, 2010 8:38 am

So you wouldn’t sell your soul for a ‘clever’ proof that P != NP?

25. August 19, 2010 8:40 am

Today’s award of the 2010 Rolf Nevanlinna Prize to Daniel Spielman is in large measure for work that Spielman and Shang-Hua Teng describe in their J. ACM article Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time. The Spielman/Teng work is exemplary of fundamental mathematic research that doesn’t yield concrete algorithms having immediate practical utility, but provides us instead with (in Dick’s words) “proofs that tell us why”.

Modern-day science and engineering relies on many mathematical tools that in practice work exceedingly well even though we don’t understand why … and in consequence, scientists and engineers share in the general longing for “proofs that tell us why” … and share also in the general rejoicing when such proofs appear.

August 19, 2010 9:33 am

How did cc.gatech get to where it was on CS theory ranking? BTW Dick with beard reminds me of an European ship captain sailing the seven seas commissioned to look for treasure and adventure half a millennium ago … He happens to be the captain (chair) at his department too and the ship seems to have hit some rough weather! But it should do fine 🙂

August 19, 2010 12:51 pm

theory @ cc.gatech.edu has seen a sea change over the last decade.
amongst many factors, prof. lipton’s move to atlanta was a triggering point defintely.

shortly before that leonard schulman had left for caltech; another fantastic researcher, and he was missed.

why does cc.gatech.edu always make me nostalgic? — ahh.. i went there…- thats right 🙂

August 20, 2010 6:22 am

🙂 That’s ok, LS is not on wiki for any reasons. If you’re not on wiki, you don’t exist! Maybe we need a wikipedia entry of list of people with no reason to be on wikipedia.

August 19, 2010 11:44 am

The blogger asked “What are your reasons” for being interested in P!=NP? Here’s one not mentioned above: It would be good for interstellar commerce!

That’s because extremely low-bandwidth conversations could still convey information that is very hard to recompute, hence rare, and hence potentially valuable. So the fact of P!=NP would be good for interstellar commerce. Evidence against P!=NP would undermine the value and the commerce. A proof of P!=NP would put that risk to rest. The same argument may apply to less extreme information bottlenecks as well.

August 20, 2010 11:15 am

Hi everybody, here are my two cents.

I totally agree that a proof of $P \neq NP$ would be highly beneficial, in the sense that it would clarify why efficient computation is affected by an intrinsic, unavoidable limit. At least, that would definitely improve our knowledge of the world we live in.

Personally, I belong to the minority of people who believes that P = NP (or, at least, who believes that P = NP is possible). I can’t bring any evidence to support such a belief, the following are nothing more than just subjective feelings:

1. I like to think that there exist an inner elegance, an implicit simplicity we can leverage in order to design a polynomial time complete algorithm for SAT. Such an inner elegance would be a necessary property of both structured and random SAT instances (let me say that, in a certain sense, random instances would only give the illusion of chaos and disorder, actually obeying some necessarily-arising hidden patterns).

2. Even the best state of the art complete SAT solvers are nothing more than very clever improvements of brute force search. I feel that a polynomial time complete algorithm for SAT, if ever invented, would need to introduce a paradigm shift: it would use some radically new (although maybe simple) strategy so far overlooked. Maybe it would be able to scan the entire search space implicitly rather than explicitly. I’m inclined to believe that there may exist some very smart syntactical transformation of the input CNF formula which always leads to the answer in polynomial time.

3. The efficiency of such an algorithm would necessarily imply its output to bring more information than usual. In other words my feeling is that, as a necessary consequence of the algorithm being poly time, its output will not be just “The instance is UNSATISFIABLE” or “The instance is SATISFIABLE, here’s a solution y”. The algorithm would answer more than what we asked, and that would be necessary for it to be efficient.

4. An algorithm like that, if ever invented, would prove more than P = NP. Moreover, as many others, I consider possible that its inventor could be an amateur (maybe someone who has not been indoctrinated with too much conventional wisdom). Maybe an amateur will design the algorithm, the community will thoroughly test it with every kind of benchmark, and then some professional researcher will formally prove it runs in poly time. Who knows.

Again, the above points are simply personal sensations. I just like to believe that they may happen to be true. Nonetheless, I’d be glad to know if anyone has comments on them.

Kind regards,

Giorgio

August 21, 2010 1:45 am

Interesting. I wonder if anybody knows the story of Linear Programming in enough detail to contrast it with your comments.

August 21, 2010 11:59 am

Thanks for your reply. Do you refer to breakthroughs by Leonid Khachiyan and Narendra Karmarkar?

August 21, 2010 7:16 am

I gave an after-dinner speech a few years ago arguing that a proof of superlinear circuit complexity for NP is essential to national security: sooner or later, space aliens will arrive on earth to judge human civilization, and our lack of progress in circuit complexity is one of the reasons that they will destroy us and repopulate the earth. (While unconcerned with our propensity to make war, they will also be disappointed with our not verifying our software and with the enormous amount of time we spend waiting in line.)

• August 21, 2010 10:30 am

Is this in jest or a kind of Poe?

August 22, 2010 5:54 am

I was serious. It was the closing dinner of a summer school and I was talking about how students should decide what kind of research to do. I suggested that in addition to thinking about how God might judge them when they die, they might consider how advanced space aliens might judge humanity should they arrive on earth. Both kinds of reflection are beneficial, for similar reasons. (Of course you need space aliens because nobody imagines a God petty enough to destroy us when we report that SAT requires at least 3n gates.)

• August 22, 2010 7:26 am

Thus definitely a POE! 😀