When I first saw the case that P != NP question is undecidable, it resonated intuitively – after all, it is a statement about proving a proposition about what you are unable to prove – most likely, you will get a lot of “isometric exercise”, in terms of mental muscles. The history of set theory shows that you can only prove this kind of thing about a simpler language than the one used to make the proof (meta language and object language).

A little later, I found an historical analogue to this problem in the writings of Poincare, before the development of Zermelo Frankl set theory (in particular, the axiom of infinity).

Poincare noted that a number of mathematicians had tried to prove mathematical induction as a theorem (he claims that even the great Hilbert fell into this trap), rather than an axiom. It looks like 2 statements.

But Poincare gave a one-line independence proof – the statement is really an infinite number of statements, P(n) -> P(n+1) for all n – but there were only a finite number of axioms at the time. So you can’t get there from here!

In the case of the P vs NP problem, you can also give one of these hand-waving arguments that P != NP, using the Hamilton Cycle problem for instance, but explain the analogy with the above, by showing that a rigorous proof would require the demonstration of the non-existence of an infinite number of algorithms, one for each degree of polynomial.

The hand-waving argument for taking this as an axiom goes like this – given an algorithm to find a Hamiltonian cycle, there will be some graph that forces the algorithm to look at every possible path before finding a Hamiltonian cycle in the worst case. Just take a graph where there is no cycle, but falls short by just the last edge. Of course the algorithm would have to look at everything before giving up. Then change the graph to include this edge. Then the algorithm would have to look at everything before finding the cycle.

But a rigorous proof would require showing that there is no O(n) algorithm for each n, and of course this won’t happen “by induction on the degree of complexity”, since these algorithms get more and more complex with increasing n.

One of my goals in the above is to give a criterion to dissuade bogus attempts at proof, by giving that “elevator speech” – in the Abstract of the Paper, “does the proof deal with the requirement of showing the non-existence of an infinite number of algorithms?”

And of course, it most likely won’t.

In other words: Gödel has shown that computer science didn’t know everything about mathematics, but the converse is also true – mathematics doesn’t know everything about computer science!

Sometimes I wonder if the impossibility to solve NP-complete problems efficiently hasn’t been an incentive for the evolution of intelligence. After all, if there existed a single method for doing everything, would anyone need to be smart?

]]>I am an occasional reader of your blog, but I must say I rather more enjoyed the paper you wrote some years ago on the topic, “Is P Versus NP Formally Independent?”

First of all, the P vs. NP question is a very difficult problem, and it does not impugn your intelligence, or the intelligence of computer scientists in general, that you cannot solve it. Even an expert could spend many years on it and become very frustrated. Sure, I can accept that it is a “fundamental hypothesis” that P != NP. All those proofs that this or that problem cannot be solved in deterministic polynomial time unless P = NP testify to that. And if you derive some important new result that you can only show to be true as long as P != NP, I doubt your peers would reject it solely on that basis.

All your evidence shows is that as far as we know it would be reasonable and useful to assume that P != NP. For the most part it is accepted as a reasonable and useful assumption, so there is no problem there. But that doesn’t mean that “P != NP” is “99% likely” to be true, or provable even if it is true. And the rest of the world wonders what exactly you mean when you try to convince us of a claimed mathematical truth by some “scientific” reasoning that falls short of mathematical proof. A “scientific” case for P != NP would require peer review, and I should hope your peers would require a proof if you stated this unequivocally.

I think academic standards are falling. Colleges have lowered the standard of proof for rape from “proof beyond a reasonable doubt” to “a preponderance of the evidence,” never mind the rights of the accused, because in many cases it’s just too difficult to actually prove rape. Now we’re supposed to believe some mathematical statement based on a preponderance of the evidence, too, where formerly a proof was required, just because this particular statement happens to be really hard to prove. The academic world is going mad.

]]>http://www.informit.com/articles/article.aspx?p=2213858&WT.mc_id=Author_Knuth_20Questions

and more follow up here.

http://www.reddit.com/r/compsci/comments/262tw7/knuth_on_why_he_believes_pnp_question_17/

http://rjlipton.wordpress.com/2014/02/28/practically-pnp/#comment-53223

http://rjlipton.wordpress.com/2014/02/28/practically-pnp/#comment-53252

Had trouble with WordPress over there, so let me clarify where WP mucked it up… Paragraphs 4 and 5 can be combined/simplified as below:

The generic expression for the OFC is “f(X) is at least K” for maximization based problems and “f(X) is at most K” for minimization based problems… Each of these conditions will take a bunch of clauses to express.

]]>This might be a bit off topic, but how does it come that in the anglophone world, “science” is often used as a synonym for “natural science”?

Looking at the origin of the word, it derives from the latin word for “knowledge”. Similarly, the German term “Wissenschaft” derives from “Wissen schaffen” which roughly translates to “establishing knowledge”. That said, it seems pretty obvious to me that not only natural sciences, but also formal sciences as math are establishing knowledge. Thus, categorizing physics as science, but math as some kind of non-science, seems a bit crude to me.

Furthermore, I am not fully convinced that math and “reality” are as unrelated as sometimes suggested. Picking up a question raised by Scott elsewhere, a world in which 2+2=4 does not hold, appears rather unthinkable to me – at least if we identify sums of natural numbers with the number of elements in the union of two disjoint sets, and if we identify sets with collections of distinguishable objects in reality.

]]>