A future proof of \(P=NP\) or \(P\neq NP\) may be far-reaching or not so much

A few days ago, Norbert Blum, a professor (and a chair) from Bonn, the ex-capital of West Germany (picture) whose publication record looks good released the preprint

A Solution of the P versus NP Problem

claiming to contain a proof that \(P\neq NP\).

John Baez and Alon Amit, a brilliant mathematician at Quora, have offered their opinions. The preprint isn't "self-evidently wrong" according to some basic "smell tests" that may be used to "sniff" for wrong proofs of this kind, Baez concluded. In fact, a bunch of computer scientists has so far reacted in the same way: it looks rather credible so far. So it's good enough news for Blum.

At the same moment, neither Baez nor Amit could tell us "I have found a clear mistake" or, on the contrary, "I have verified the proof and joined those who claim that a proof has been found". Francis Villatoro, Gary Knife, and Scott Aaronson claim to know about incorrect statements "proven" at places in Blum's proof, however, although they don't know where's the error in Blum's proof. Sadly for Scott Aaronson who offers you $200,000 if he is wrong, he was mindlessly building on a statement by Luca Trevinsan who has already renounced his own criticism (he misunderstood what Andreev's function was).




So we don't have too clear verdicts on the validity of the proof of \(P\neq NP\) that Blum proposes – and yes, it's a proof of the inequality. In a couple of days, many more computer scientists will have read Blum's preprint and we will start to be exposed to some outspoken opinions of one kind or another.




I have repeatedly written that \(P=NP\) is a proposition without a precedent (which can't be representatively clumped with lots of "analogous" propositions so that the probability could be estimated in a frequentist fashion), so without a full proof, we must be open-minded and admit that both answers are possible. Collectively, we should respect the fact that both answers are "comparably likely", i.e. reserve comparable resources to the people with both biases, otherwise something is dishonest about the institutions running this kind of research.

But there's another statement similar to the belief "\(P\neq NP\) has to be believed, otherwise you're a nasty heretic and moron" that I want to heavily denounce. It is this comment by Alon Amit:

Update: I don’t think this paper will stand up to scrutiny. A profound theorem which has been as massively researched as as \(P\neq NP\) will, in all likelihood, be solved with deep and far-reaching new techniques. It’s not impossible that it will be solved with a slight enhancement of known, existing methods, but it’s just very, very, very unlikely.

According to everything I know about mathematics and the world of logical reasoning, this statement by Amit is absolutely irrational.

Norbert Blum claims exactly what Amit labels as "very, very, very unlikely", and even a few days after the publication, it still looks conceivable: Blum's proposed proof of \(P\neq NP\) is a minor variation of some previous inequality in the literature. He claims to generalize some inequalities for "monotone network complexities" to "non-monotone network complexities". It may be right or wrong. But there are so many possible generalizations of existing papers (the number is almost certainly much higher than the number of people who have actually studied the papers that Blum builds upon) that it is absolutely conceivable that the right generalization that leads to a proof hasn't been found by anyone before Blum and that Blum – or someone else – turns out to be the person who settles the Clay Institute $1 million problem.

I want to argue for a while. Amit basically says that "no one can find a proof because no one has found it before". This is rubbish. No one had found relativity before Einstein – and it's true that no invention and no discovery was ever invented or discovered before the first inventors or discoverers. So what the hell he is talking about? It's totally possible that Blum has been searching in the right region of the space of ideas just like Einstein was searching in the right region while he was discovering relativity.

Blum's paper isn't particularly trivial – the PDF document has 38 pages. Now, does Amit claim to have a proof that a proof of \(P=NP\) or \(P\neq NP\) has to have more pages (or many more pages) than 38? Could he please show us this proof? Would 380 pages be enough? Or can Amit prove that the person who solves this problem has to be from a larger or more famous city than Bonn? ;-) It's spectacularly obvious that he can't have any proof like that – such a proof would almost certainly have to be more messy than the proof of \(P=NP\) or \(P\neq NP\) itself. It's spectacularly clear that what Amit writes is nothing else than a prejudice, a part of a religion.

Moreover, the experience has taught us that clever advances are often very simple, much simpler than all the previous hopeless attempts. Would Amit disagree? For example, relativity is simpler than the models of the aether that it has debunked and superseded. But even if you decided to believe that a proof has to be longer than most of the previous failed attempts, Blum's proof could still work because there have been not too many attempts like that which were 38-page-long or longer.

And let me say that a part of this religion is somewhat irreligious, financially motivated. Why? Because tens of thousands of people have been paid for a very long time by doing complexity theory research that has been marketed as a "bunch of generalizations of \(P\) versus \(NP\)". So because billions of dollars have been paid to these people and they haven't settled the iconoclastic proposition yet, and what they have obtained looks like a pile of random technicalities, they feel some bad conscience and they are promoting this pledge that "we will surely find something stunning". Except that unlike the case of string theory, there exists absolutely no rational evidence that there exists something stunning waiting to be discovered.

In fact, it's even plausible that these people don't want the \(P\) versus \(NP\) problem to be settled because something would be over and they could lose their funding – partly justified by their search for the \(P=NP\) holy grail.

The question about \(P\) versus \(NP\) is just a random question you may ask about complexity – yes, a simple enough question and one that can't be settled really easily, apparently – and whether the posing of a random question like that leads to some deep research or insights or methods has a random answer. Amit's claim that a proof of \(P\) versus \(NP\) has to revolutionize all of mathematics and bring us warp drive and a cure for all diseases etc. is just absolutely indefensible by rational arguments. The promotion of such statements is a religion. A religion whose propagation is in the interest of a special interest group.

So I am very interested in analyses of the paper and even incomplete opinions about its truth value. However, I am really not waiting for idiotic opinions of the kind "a proof of \(P\neq NP\) is obliged to be a holy grail that causes the second coming of Jesus Christ" because I believe that a rational, unbiased person has done the work to assure himself that the speaker can't possibly have any evidence for such a claim so the would-be authoritative statement is just a fallacy that is considered illegitimate in a reasonable discussion.