New application for solving the problem P vs. NP

The other day Norbert Blum published a preprint on the archive entitled “A Solution of the P versus NP Problem”. Thus, Blum claims to be resolved in one of the tasks of the millennium , for which, in addition to honors, $ 1 million is required. In this article, I have compiled a small summary of this.

What is proved?

The problem of equality of the classes P and NP can be informally defined as follows:

If a positive answer to a question can be quickly (in polynomial time) checked (using some supporting information called a certificate), is it true that the answer itself (along with the certificate) to this question can be quickly found? Tasks of the first type belong to the class P, the second - to the class NP. The problem of equality of these classes is one of the most important problems of the theory of algorithms. (Wikipedia)

The Blum article proves a stronger statement:

For the task of checking whether there is a given size in the click graph (a full subgraph) of a given size, there are no boolean schemes (Boolean networks) of polynomial size.

From this statement it follows that P ≠ NP. Indeed, if P = NP, then for each task from NP (including for checking a click) there is a polynomial algorithm, and a polynomial algorithm can be transformed into a family of Boolean circuits of polynomial size. Thus, if for some problem from NP there are no Boolean schemes of polynomial size, then P ≠ NP.

Why the fact of the appearance of evidence is not surprising

As with any other well-known mathematical problem, proofs of P = NP or P ≠ NP appear with enviable regularity — you can see a selection of 100+ proofs on this site . However, not all of them attract the attention of the scientific community. The last time this happened 7 years ago, when Vinay Deolalikar published his evidence, but also found an error in his proof.

Why did Blum's evidence attract attention?

First, Norbert Blum is a well-known and respected scientist who is at the same time famous for his meticulousness. It is doubtful that he would publish this article if he were not 100% sure of its correctness. Secondly, the proposed technique bypasses all known limitations on the proof of P ≠ NP. The fact is that in the theory of complexity there is a series of statements like “such a technique cannot prove P ≠ NP” (Natural Proofs, relativization, algebraization), but the proposed technique neatly avoids all these limitations.
')
The only serious argument against this proof at the moment is that this article looks too simple for such a result. Surprisingly, such a difficult problem is resolved in a 30-page article. Indeed, compared with the proofs of Wiles (Fermat's Big Theorem), Perelman (Poincare conjecture), and even with the recent result of Babai (a quasi-polynomial algorithm for graph isomorphism), Blum's proof looks incredibly simple and short. On the other hand, this may have an explanation - Blum does not prove from scratch, but develops the technique of Berg and Ulfberg, which in turn is based on the breakthrough results of Razborov, Andreev and Tardosh, that is, it may turn out that "everything complicated" has already been done before, and it remained only to "add a puzzle."

What will happen now?

Nothing special. Most likely after some time, an article will find an error, as has happened in all previous cases. Moreover, it is possible (but very unlikely) that Blum did prove that P NP. In this case, the verification of the article will take quite a lot of time - the article will not be recognized as valid until the experts in this field do not analyze the entire result by brick and check its accuracy thoroughly.

Current state of affairs

The main discussion takes place on StackExchange - all the comments are collected there and the places where errors may occur are determined. There is also a thread on Quora and some discussion in the comments to the post of Luca Trevissan.

If you want to understand in more detail what is happening, then read the posts of Luke Trevissan and Richard Lipton .

Explanation from "non-specialist" can be found here .

While most experts are skeptical. For example, a well-known expert on complexity and quantum computing, Scott Aaronson , would have put $ 200 thousand on the fact that the proof is not true. By the way, Scott Aaronson has an interesting set of 10 tests that allow you to determine whether an article deserves some serious problem, attention. As far as I understand, the article of Blum passes all these tests, except the last one: the proposed proof looks too simple.

Update : While I was writing this post, a comment appeared in the discussion on StackExchange stating that Alexander Razborov (on whose results Blum's evidence is based) had already looked at the article and found the reason why this evidence should be erroneous .

Update 2: A description of the error has appeared , which is probably fatal for proof.