Norbert Blum recently posted a 38-page proof that $P \ne NP$. Is it correct?

Also on topic: where else (on the internet) is its correctness being discussed?

Note: the focus of this question text has changed over time. See question comments for details.


11 Answers 11


As noted here before, Tardos' example clearly refutes the proof; it gives a monotone function, which agrees with CLIQUE on T0 and T1, but which lies in P. This would not be possible if the proof were correct, since the proof applies to this case too. However, can we pinpoint the mistake? Here is, from a post on the lipton's blog, what seems to be the place where the proof fails:

The single error is one subtle point in the proof of Theorem 6, namely in Step 1, on page 31 (and also 33, where the dual case is discussed) - a seemingly obvious claim that $C'_g$ contains all the corresponding clauses contained in $CNF'(g)$ etc, seems wrong.

To explain this in more detail, we need to go into the proof and approximation method of Berg and Ulfberg, which restates the Razborov's original proof of the exponential monotone complexity for CLIQUE in terms of DNF/CNF switches. This is how I see it:

To every node/gate $g$ of a logic circuit $\beta$ (containing binary OR/AND gates only), a conjunctive normal form $CNF(g)$, a disjunctive normal form $DNF(g)$, and approximators $C^k_g$ and $D^r_g$ are attached. $CNF$ and $DNF$ are simply the corresponding disjunctive and conjunctive normal forms of the gate output. $D^r_g$ and $C^k_g$ are also disjunctive and conjunctive forms, but of some other functions, "approximating" the gate output. They are however required to have bounded number of variables in each monomial for $D^r_g$ (less than a constant r) and in each clause for $C^k_g$ (less than a constant k).

There is notion of an "error" introduced with this approximation. How is this error computed? We are only interested in some set T0 of inputs on which our total function takes value 0, and T1 of inputs on which our total function takes value 1 (a "promise") . Now at each gate, we look only at those inputs from T0 and T1, which are correctly computed (by both $DNF(g)$ and $CNF(g)$, which represent the same function - output of gate $g$ in $\beta$) at gate output, and look how many mistakes/errors are for $C^k_g$ and $D^r_g$, compared to that. If the gate is a conjunction, then the gate output might compute more inputs from T0 correctly (but the correctly computed inputs from T1 are possibly decreased). For $C^k_g$, which is defined as a simple conjunction, there are no new errors however on all of these inputs. Now, $D^r_g$ is defined as a CNF/DNF switch of $C^k_g$, so there might be a number of new errors on T0, coming from this switch. On T1 also, there are no new errors on $C^k_g$ - each error has to be present on either of gate inputs, and similarly on $D^r_g$, switch does not introduce new errors on T1. The analysis for OR gate is dual.

So the number of errors for the final approximators is bounded by number of gates in $\beta$, times the maximal possible number of errors introduced by a CNF/DNF switch (for T0), or by a DNF/CNF switch (for T1). But the total number of errors has to be "large" in at least one case (T0 or T1), since this is a property of positive conjunctive normal forms with clauses bounded by $k$, which was the key insight of Razborov's original proof (Lemma 5 in the Blum's paper).

So what did Blum do in order to deal with negations (which are pushed to the level of inputs, so the circuit $\beta$ is still containing only binary OR/AND gates)?

His idea is to preform CNF/DNF and DNF/CNF switches restrictively, only when all variables are positive. Then the switches would work EXACTLY like in the case of Berg and Ulfberg, introducing the same amount of errors. It turns out this is the only case which needs to be considered.

So, he follows along the lines of Berg and Ulfberg, with a few distinctions. Instead of attaching $CNF(g)$, $DNF(g)$, $C^k_g$ and $D^r_g$ to each gate $g$ of circuit $\beta$, he attaches his modifications, $CNF'(g)$, $DNF'(g)$, ${C'}^k_g$ and ${D'}^r_g$, i.e. the "reduced" disjunctive and conjunctive normal forms, which he defined to differ from $CNF(g)$ and $DNF(g)$ by "absorption rule", removing negated variables from all mixed monomials/clauses (he also uses for this purpose operation denoted by R, removing some monomials/clauses entirely; as we discussed before, his somewhat informal definition of R is not really the problem, R can be made precise so it is applied at each gate but what is removed depends not only on previous two inputs but on the whole of the circuit leading up to that gate), and their approximators ${C'}^r_g$ and ${D'}^r_g$, that he also introduced.

He concludes, in Theorem 5, that for a monotone function, reduced $CNF'$ and $DNF'$ will really compute 1 and 0 on sets T1 and T0, at root node $g_0$ (whose output is the output of the whole function in $\beta$). This theorem is, I believe, correct.

Now comes the counting of errors. I believe the errors at each node are meant to be computed by comparing reduced $CNF'(g)$ and $DNF'(g)$ (which are now possibly two different functions), to ${C'}^r_g$ and ${D'}^k_g$ as he defined them. The definitions of approximators parrot definitions of $CNF'$ and $DNF'$ (Step 1) when mixing variables with negated ones, but when he deals with positive variables, he uses the switch like in the case of Berg and Ulfberg (Step 2). And indeed, in Step 2 he will introduce the same number of possible errors like before (it is the same switch, and all the involved variables are positive).

But the proof is wrong in Step 1. I think Blum is confusing $\gamma_1$, $\gamma_2$, which really come, as he defined them, from previous approximators (for gates $h_1$, $h_2$), with positive parts of $CNF'_\beta(h_1)$ and $CNF'_\beta(h_2)$. There is a difference, and hence, the statement "$C_g'$ contains still all clauses contained in $CNF'_\beta(g)$ before the approximation of the gate g which use a clause in $\gamma_1'$ or $\gamma_2'$" seems to be wrong in general.

  • 2
    $\begingroup$ seems to be same comment on RJL blog rjlipton.wordpress.com/2017/08/17/… did you write that? wanted to add an idea: what if the key is to consider T0/T1 of all equal 1-bits wrt cnf-dnf conversion/ approximation? it is known by Berkowitz 1982 this is sufficient to separate P vs NP see "complexity of slice functions"/ wegener sciencedirect.com/science/article/pii/0304397585902099 $\endgroup$ – vzn Aug 18 '17 at 16:14
  • 6
    $\begingroup$ @vzn The author of this comment on the blog is "vloodin." The author of this answer is "idolvon." A permutation of the letters gives a hint the authors are not too different. $\endgroup$ – Clement C. Aug 19 '17 at 1:56
  • 2
    $\begingroup$ Just curious, has there been any sort of further public communication from Blum after uploading the paper to the arxiv? $\endgroup$ – Matt Aug 22 '17 at 20:23
  • 9
    $\begingroup$ @Matt Blum retracted the paper and posted the following comment on the arXiv page of the paper: "The proof is wrong. I shall elaborate precisely what the mistake is. For doing this, I need some time. I shall put the explanation on my homepage" $\endgroup$ – Gustav Nordh Aug 31 '17 at 5:52
  • $\begingroup$ This answer has been confirmed as correct by Scott Aaronson, citing other (unnamed) reviewers: scottaaronson.com/blog/?p=3409 $\endgroup$ – cuniculus Sep 7 '17 at 20:22

I am familiar with Alexander Razborov whose previous work is extremely crucial and serves as a foundation for Blum's proof. I had the good luck of meeting him today and wasted no time in asking for his opinion on this whole matter, on whether he had even seen the proof or not and what are his thoughts about it if he did.

To my surprise, he replied that he indeed was aware of Blum's paper but didn't care to read it initially. But as more fame was given to it, he did get a chance to read it and detected a flaw immediately: namely that the reasonings given by Berg and Ulfberg hold perfectly for the function of Tardos, and since this is so, Blum’s proof is necessarily incorrect as it contradicts the core of Theorem 6 in his paper.

  • 2
    $\begingroup$ It would be great if you could elaborate on this. Is Tardos' function known to be in P? $\endgroup$ – Thomas Aug 17 '17 at 22:02
  • 5
    $\begingroup$ Tardos function is in P, and is an approximation of Lovasz theta function, which, for a graph complement, is between clique number and chromatic number. Lovasz theta real function is monotone function of a graph. However, the question is weather this approximation gives rise to a monotone function of a graph too (only monotone function would invalidate the proof). Can someone give us the reference to the Tardos paper where this is defined, please? $\endgroup$ – idolvon Aug 17 '17 at 22:30
  • 7
    $\begingroup$ @idolvon You mean this: cs.cornell.edu/~eva/… It explicitly states that the function φ is poly-time computable monotone function $\endgroup$ – PsySp Aug 17 '17 at 22:40
  • 12
    $\begingroup$ Thanks! That basically settles it - the Bloom's proof must be wrong. Now, it might be interesting to pinpoint a mistake. I'll look into it and post a comment on lipton's, as in good old days, according to prof. p Woodpecker's wishes. $\endgroup$ – idolvon Aug 17 '17 at 23:14
  • 1
    $\begingroup$ @idolvon Yes, I thought so too. Blum's arguments should carry over function φ as defined in that paper which states that is monotone and polytime computable (trivial by its definition). $\endgroup$ – PsySp Aug 17 '17 at 23:21

This is posted as community answer because (a) it's not my own words, but a citation from Luca Trevisan on a social media platform or from other people with no CSTheory.SE account; and (b) anyone should feel free to update this with updated, relevant information.

Quoting Luca Trevisan from a public Facebook post (08/14/2017), replying to a question about this paper asked by Shachar Lovett:

Andreev's function, which is claimed to have superpolynomial circuit complexity (abstract, then section 7), is just univariate polynomial interpolation in a finite field, which, if I am not missing something, is solvable by Gaussian elimination

Actually, this is not necessarily a point where the proof fails; Luca then answered the following (08/15/2017), after a question related to Andrew's comment below:

You are right, guys, I misunderstood the definition of Andreev's function: it's not clear that it reduces to polynomial interpolation

Karl Wimmer commented on the point raised by Gustav Nordh (reproduced with Karl's permission):

To add to this, I don’t see why, from the first two paragraphs of the proof of Theorem 5, we can conclude that $\mathrm{DNF'}(g_0)$ computes $f$. I see only some sort of one-sided-ness that $\mathrm{DNF'}(g_0)$ computes a function such that $f = 1$ implies that this function is also 1.

The third paragraph doesn’t help me either: surely $\mathrm{DNF'}(g_0)$ and its DNF/CNF-switch compute the same function, but it does not immediately follow that the DNF/CNF-switch computes $f$ (because $\mathrm{DNF'}(g_0)$ might not), so we can’t make any conclusions about $f$-clauses.

(Aside: this one-sided-ness is consistent with Gustav’s example above.)

From a different viewpoint, surely a standard network computing a monotone function could compute non-monotone functions at internal nodes. Theorem 5 doesn’t apply to non-monotone functions, so $\mathrm{DNF'}(g)$ might not correctly compute the sub-function in the network whose output node is $g$ (which will happen for many non-monotone functions). Because of this, I’m not convinced that this inductive construction of $\mathrm{DNF'}(g_0)$ will necessarily be correct in the end.

If I’m totally off-base here, please let me know!

From an anonymous user, in reaction to Karl's point:

DNF' and CNF' are just DNF and CNF for f, in which cancellations of opposite literals are done, hence reducing them to shorter form. This is also explained in the paper, and it is somewhat cumbersome from the definition but that is what it is. Theorem 5 is not the problem, meat is in the Theorem 6.

And the answer by Karl (which I reproduce again here):

I see what anon is saying (thanks!); my comment didn't properly address my confusion. If $f$ is monotone and computed at $g_0$, it is fine to take $\mathrm{DNF}(g_0)$, apply absorption and the $R$ operator, and the resulting $\mathrm{DNF'}(g_0)$ represents $f$. Using this "one-shot" construction, Theorem 5 is fine--on to Theorem 6. I glossed over this definition of $\mathrm{DNF'}(g_0)$

What I can't see is why the gate-by-gate apply-absorption-and-$R$-as-you-go construction of $\mathrm{DNF'}(g_0)$ on pages 27-28 does the same thing. This seems necessary for the gate-by-gate analysis in Theorem 6 to work, unless error from this construction is accounted for. I mean, not every function can even be represented by a DNF with terms with only non-negated or negated literals, but for each node $g$, $\mathrm{DNF'}(g)$ seems to always have this form. What if there is a node $g$ in my network such that $\mathrm{res}(g)$ has no such representation?

(Another small (?) point: I don't see what $R$ does in the gate-by-gate as-you-go construction; in 1.-4., it seems like $\alpha$ is already the standard DNF construction, but with absorption and $R$ applied.)

(answer from anon) I agree that vagueness in definition of R might be a problem in section 6. R is not explicitly defined, and unless its action depends somehow on the whole DNF (and not on the values of DNF' at gates inductively), there might be a problem. Deolalikar's proof had similar problem - two different definitions were confused. Here, at least we know what is meant to be DNF', and if this is source of the problem in section 6, it can be easy to track. I didn't go into section 6 yet though, it requires understanding proof by approximators by Berg and Ulfberg described in section 4, ultimately related to Razborov's construction from 1985, which is not easy.

Explanation how R works:

When R is applied in some step, it only cancels terms which, AT THAT STEP, would contain opposite literals (we might need to track negative literals). For instance, lets evaluate $$(x\lor y) \land (\lnot x \lor y) \land (x \lor \lnot y)$$ as $$((x\lor y) \land (\lnot x \lor y))\land (x \lor \lnot y)$$ first, to compute DNF' at first AND node, we get $$(x\lor y) \lor ((x\land y)\lor (y\land y))$$ before applying R, but after applying R we lose the first $x$ from the first bracket, and get $$(y) \lor (x\land y)\lor (y),$$ (where the first $y$ might have virtual NOT $x$ if we were tracking it). Then apply the second AND, to get $$((y) \lor (x\land y)\lor (y)) \lor ((x\land y)\lor (x\land y) \lor (x\land y)),$$ but then R removes the whole first bracket because it has virtual NOT y present (in this case we didn't need to keep track of the previous steps, but perhaps we need in general), leaving $$((x\land y)\lor (x\land y) \lor (x\land y))$$ or simply $$(x\land y)$$

  • 6
    $\begingroup$ I am skeptical of this (but don't use Facebook to say anything there)--Andreev's function (in the paper) is given as a bipartite graph with left and right vertex sets equal to GF(q), plus an arbitrary edge set, and a degree bound. The question is whether there is a way to choose, for each vertex on the left, one of its neighbors, so that the induced function (from left to right) is a low-degree polynomial. Luca's comment applies once we have a good choice of neighbor for each left vertex (as then it's just polynomial interpolation), but it's not clear to me how to make a good choice. $\endgroup$ – Andrew Morgan Aug 15 '17 at 14:54
  • $\begingroup$ @AndrewMorgan I updated the CW answer. $\endgroup$ – Clement C. Aug 15 '17 at 16:03
  • $\begingroup$ @Karl Wimmer: regarding weather DNF′(g0) computes f, one needs to use that f is monotone, I think. It is assumed in Theorem 5 that f is monotone. $\endgroup$ – idolvon Aug 15 '17 at 23:43
  • $\begingroup$ confused! is this all quoting from the facebook post? on clicking shachar lovett facebook link above, some of the above replies are visible to me but others are not visible for me. eg Karl Wimmer. is this due to some screening of friend responses in facebook? if so this is disappointing & its not a very good place for public discussion. maybe someone can make a screenshot? :( or are you citing stuff from outside the facebook post? plz be careful/ complete with citations/ urls $\endgroup$ – vzn Aug 17 '17 at 17:02
  • $\begingroup$ oh! further research you are also quoting replies from baez blog post which contains Wimmers reply etc johncarlosbaez.wordpress.com/2017/08/15/… $\endgroup$ – vzn Aug 17 '17 at 17:33

The correctness of the claimed proof is being discussed at Luca Trevisan's blog: https://lucatrevisan.wordpress.com/2017/08/15/on-norbert-blums-claimed-proof-that-p-does-not-equal-np/

In particular "anon" posted the following relevant comment:

"Tardos observed that Razborov’s and Alon-Boppana’s arguments carry over to a function which is computed by a polynomial size non-monotone circuit (the function is a small variant on approximating the Lovasz theta function of the graph). If Berg and Ulfberg’s arguments also apply for Tardos’ function (which is intuitively likely, as their proof seems to be based on Razborov’s proof) then it is clear that that Blum’s current claim cannot be correct. Unfortunately, the author does not discuss this point."

On a direct question from "Mikhail", Alexander Razborov confirms this (see Mikhail's post): the reasonings given by Berg and Ulfberg hold perfectly for the function of Tardos, and since this is so, Blum’s proof is necessarily incorrect as it contradicts the nucleus of the sixth theorem in his paper. - A. Razborov

In my opinion this definitely settles the question of whether the paper is correct or not (it is NOT correct!). It is also important to note that it seems difficult to repair the proof as the proof method itself seems flawed.

Update (2017/08/30) Norbert Blum posted the following comment on his arXiv page:

The proof is wrong. I shall elaborate precisely what the mistake is. For doing this, I need some time. I shall put the explanation on my homepage

  • 3
    $\begingroup$ I posted this as an answer as I don't have privileges yet to post comments. $\endgroup$ – Gustav Nordh Aug 16 '17 at 7:44
  • 11
    $\begingroup$ Yes, this is my understanding (but I may be wrong). Tardos' function is a monotone function which is 1 on k-cliques and 0 on complete (k-1)-partite graphs. As far as I can tell, Berg and Ulfberg use ONLY these properties in their CNF-DNF approximation proof for CLIQUE, which hence prove that Tardos' function has exponential monotone complexity. Blum's Theorem 6 says that monotone complexity lower bounds by CNF-DNF approximation for monotone functions, give the same NON-monotone lower bound. Hence, Tardos' function have exponential complexity according to Theorem 6 (which is false). $\endgroup$ – Gustav Nordh Aug 16 '17 at 15:16
  • 5
    $\begingroup$ In that case, it looks like settling this point should be a main focus right now... I don't believe I am competent or knowledgeable enough to do so, but (fingers crossed, which does not help the typing) others are. $\endgroup$ – Clement C. Aug 17 '17 at 0:29
  • 3
    $\begingroup$ Where is this Tardos function defined, can someone give reference to the paper? Clearly, a non-monotone functions that separate T0 and T1 exist that are in P (its easy to construct one say checking if we have a complete graph with k nodes), but is Tardos function monotone? If monotone, and separates T0 and T1, it would invalidate the proof. But if it is not monotone, than proof might still be correct. $\endgroup$ – idolvon Aug 17 '17 at 18:14
  • 4
    $\begingroup$ Tardos' function is defined in her very short paper located here: cs.cornell.edu/~eva/… Moreover the properties of Tardos' function is discussed in detail in [S. Jukna, Boolean Function Complexity p. 272] $\endgroup$ – Gustav Nordh Aug 17 '17 at 23:39

Gustav Nordh commented on by Theorem 5 (page 29). Specifically, the function

$$(x\lor y) \land (\lnot x \lor y) \land (x \lor \lnot y)$$

computes the function which is $1$ only if $x$ and $y$ are both $1$, hence it is monotone. The expression above for the function represents a "standard network" $\beta$ (where the only negations are to a literal) whose nodes corresponds to the literals $x$ and $y$, their negations, and each of the binary expressions. Suppose the output node of the network $\beta$ is called $g_0$.

The Blum paper creates a new disjunctive normal form $DNF'_{\beta}(g_0)$ from $\beta$ which appears to be

$$x\lor y \lor (x\land y)$$

Now, according to Theorem 5, each monomial in $DNF'_{\beta}(g_0)$ is an implicant of $f$. But one of the monomials in $DNF'_{\beta}(g_0)$ is $x$, which is not an implicant of $f$ (because $x=1$ does not imply $f(x,y)=1$), contradicting the Theorem. However, as noted in the comments attributed to Gustav Nordh and the detailed explanation by idolvon, this apparent discrepancy is resolved by appropriate and expansive interpretation of the term "originates" in the definition of the reduction operator $R$.

  • 2
    $\begingroup$ It appears that DNF' for this formula is (x AND y) - form full DNF, cancel trivial terms, and apply absorption $\endgroup$ – idolvon Aug 15 '17 at 23:15
  • 2
    $\begingroup$ @idolvon You are correct using the alternative definition on page 29. But the main definition of $DNF'$ is on pages 27-28, and by that definition Nordh's original analysis is correct. I am not going to leap around the paper and try and second-guess what the author intended, particularly when the text of the definition on pages 27-28 is very clear in this case. Also, other proofs in the paper use the pp. 27-28 definition, not the "alternative definition" on page 29. $\endgroup$ – kdog Aug 16 '17 at 1:05
  • 2
    $\begingroup$ The definition on pages 27-28 involves use of operator R, which is not defined except for vague phrase "originates in trivial monomial". If we take that to mean "would be canceled if literals were kept up to this stage", then the definitions are the same. In any case you would need SOME interpretation for R. Since R is so crucial in chapter 6, the right interpretation is important, and there is in fact one which is inductive. $\endgroup$ – idolvon Aug 16 '17 at 4:09
  • 2
    $\begingroup$ When R is applied in some step, it only cancels terms which, AT THAT STEP, would contain opposite literals (we might need to track negative literals). For instance, lets evaluate $$(x\lor y) \land (\lnot x \lor y) \land (x \lor \lnot y)$$ as $$((x\lor y) \land (\lnot x \lor y))\land (x \lor \lnot y)$$ first, to compute DNF' at first AND node, we get $$(x\lor y) \lor ((x\land y)\lor (y\land y))$$ before applying R, but after applying R we lose the first $x$ from the first bracket, and get $$(y) \lor (x\land y)\lor (y),$$ $\endgroup$ – idolvon Aug 16 '17 at 4:45
  • 2
    $\begingroup$ (where the first $y$ might have virtual NOT $x$ if we were tracking it). Then apply the second AND, to get $$((y) \lor (x\land y)\lor (y)) \lor ((x\land y)\lor (x\land y) \lor (x\land y)),$$ but then R removes the whole first bracket because it has virtual NOT y present (in this case we didn't need to keep track of the previous steps, but perhaps we need in general), leaving $$((x\land y)\lor (x\land y) \lor (x\land y))$$ or simply $$(x\land y)$$ $\endgroup$ – idolvon Aug 16 '17 at 4:45

Could one use list decoding of Reed-Solomon codes to show Andreev's POLY function is in P, similar to the way Sivakumar did in his membership comparable paper? Or is the POLY function known to be NP-complete?

  • 10
    $\begingroup$ Lance, I don't the answer to your questions. In June 1986, David Johnson's "Open Problem of the Month" asked whether Andreev's problem is NP-complete. See David's NP-completeness column in the Journal of Algorithms 7:2, pp. 289-305. Not sure if there was ever a resolution. $\endgroup$ – Ravi Boppana Aug 16 '17 at 21:56
  • 1
    $\begingroup$ Johnson's 1986 article predates the polynomial reconstruction techniques and list-decoding results of the 90s. $\endgroup$ – Lance Fortnow Aug 17 '17 at 13:43
  • 1
    $\begingroup$ Here's my idea using the notation in Section 7 of Norbert Blum's paper. A polynomial p that is a solution to the POLY problem could be viewed as a Reed-Solomon codeword. Choose a function f by randomly choosing an edge from each vertex in A. That f should agree with p in significantly more than a 1/q fraction of the inputs. Then we can use list decoding on f to create a polynomially long list of possibilities for p and we can check each of them. $\endgroup$ – Lance Fortnow Aug 17 '17 at 13:53
  • 1
    $\begingroup$ Unless I am misunderstanding your algorithm, using the Guruswami-Sudan algorithm, one can list-decode if the number of agreements is at least $\sim \sqrt{qd}$, where $d$ is the degree of $p$, and we are interested in the case when $d \sim \sqrt{\frac{q}{\log q}}$, which means that we need a lot more than a $\frac{1}{q}$ fraction agreement. $\endgroup$ – user1694 Aug 17 '17 at 18:04
  • 4
    $\begingroup$ @Matt Assuming I read the above correctly, that function is the one Blum for which claims to have proven superpolynomial circuit complexity. But if it is in P, it must have polynomial circuit complexity, contradicting the purported P vs. NP proof. $\endgroup$ – Clement C. Aug 17 '17 at 20:25

He has updated his arXiv to say his proof is incorrect:

The proof is wrong. I shall elaborate precisely what the mistake is. For doing this, I need some time. I shall put the explanation on my homepage.


Lipton and Regan's blog here has a nice high level discussion with an interesting comment on the proof structure.

They also point out Blum's pedigree as having proved a lower bound on Boolean circuit complexity that stood for more than 30 years. This of course is just "side information" since experts are already seriously studying the proof.


Also, here: https://www.quora.com/Whats-the-status-of-Norbert-Blums-claim-that-operatorname-P-neq-operatorname-NP

Quoting Alon Amit:

(personal opinion, Aug 14, later in the day): I don’t think this paper will stand up to scrutiny. A profound theorem which has been as massively researched as as P≠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.

  • 11
    $\begingroup$ That's a non-argument (a valid opinion, and one that I admit I share, but not a valid argument, which is what I believe we should have here). This kind of things has happened before. $\endgroup$ – Clement C. Aug 16 '17 at 13:36
  • 8
    $\begingroup$ Yes, I was not arguing anything. Simply answering the question "where is this paper discussed", and then summarizing the said discussion up to this point. $\endgroup$ – Jack Aug 16 '17 at 14:08

It is unlikely to be correct for the following reason: the method of approximations is general enough that any lower bound can be proven using them. This is a result due to Razborov. Why is it a problem? Because it means that method of approximations will not be the main progress, it can express anything, the meat will be somewhere else. There does not seem to be such meat in the paper, which suggests that most likely the author is making a subtle mistake, the kind of mistake that is hidden from the eye but essentially is an assumption that implies the answer. For those who are not complexity theorists: this is a very good smell test, it is as likely to be true as someone's claim to build a rocket at his basement to travel to moon in a week.

So where is that subtle mistake? On Trevisan's blog there is a comment by Lovett suggesting what that hidden assumption might be in theorem 6.

  • $\begingroup$ nice/ relevant point; fyi razborovs "no go" thm is "on the method of approximations" (1989) people.cs.uchicago.edu/~razborov/files/approx.pdf but feel this proof is not very well analyzed. one has to carefully understand if its stated conditions hold beyond merely the words "method of approximations" which has gone thru revisions/ developments/ refinements etc since its origination by razborov. these exact conditions are apparently not much analyzed by later researchers. the other major barrier is by razborov/ rudich natural proofs en.wikipedia.org/wiki/Natural_proof $\endgroup$ – vzn Aug 18 '17 at 14:11
  • $\begingroup$ downvoted because the content of this answer was already addressed in previous answers. $\endgroup$ – verifying Aug 19 '17 at 2:25

Blum uses Razborov´s method of approximation to conclude that a function in $NP-c$ can´t be computed in $P$.

The goal of Razborov´s method of approximation is to show that $C$ cannot compute $f$, where $f$ is a boolean function and $C$ any circuit of $m$ gates.

A boolean function has an only one truth table but not a single algebraic expression, neither a problem has only one boolean function that solves it.

Some (may be all) functions are isomorphics (problems aren´t).

To conclude that $NP=P$ by Razborov´s method of aproximation, it requieres to proof that a circuit with $m$ gates (such as $m$ is polinomic respect de entries of $f$) can´t compute a $f$ function with no isomorphims, or else that $f$ is it´s minimal isomorphism.


Not the answer you're looking for? Browse other questions tagged or ask your own question.