<p>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. </p>

<p>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 <strong>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.</strong></p>

CC BY-SA 3.0
2017-08-17T22:02:31.877Z
It would be great if you could elaborate on this. Is Tardos' function known to be in P?
Thomas Steinke
CC BY-SA 3.0
2017-08-17T22:30:07.523Z
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?
idolvon
CC BY-SA 3.0
2017-08-17T22:40:05.473Z
@idolvon You mean this: http://www.cs.cornell.edu/~eva/Gap.Between.Monotone.NonMonotone.Circuit.Complexity.is.Exponential.pdf
It explicitly states that the function φ is poly-time computable monotone function
PsySp
CC BY-SA 3.0
2017-08-17T23:14:33.807Z
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.
idolvon
CC BY-SA 3.0
2017-08-17T23:21:31.750Z
@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).
PsySp
CC BY-SA 3.0
2017-08-19T14:44:11.120Z
great to hear from virtuoso/ pioneer/ grandmaster razborov himself even 2ndhand. but even grandmasters can have blind spots... if anyone tries to go this direction they need to study berkowitz 1982 who showed superpolynomial center slice functions lower bounds for monotone circuits are _sufficient_ to separate P vs NP. both razborov/ blum apparently have never cited berkowitz! serious researchers maybe _need to give_ up on looking at 2 slices T0, T1 and focus on a _single center one!_ Rossman 2009 points the way where to look http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.156.5526
vzn
CC BY-SA 3.0
2017-08-17T20:44:55.293Z
2017-08-18T04:16:26.530Z
2017-08-18T04:16:26.530Z
Mikhail
<p><em>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.</em></p>

<hr>

<p>Quoting <a href="https://people.eecs.berkeley.edu/~luca/" rel="noreferrer">Luca Trevisan</a> from a <a href="https://www.facebook.com/shachar.lovett/posts/10155282027901321" rel="noreferrer">public Facebook post</a> (08/14/2017), replying to a question about this paper asked by <a href="http://cseweb.ucsd.edu/~slovett/" rel="noreferrer">Shachar Lovett</a>:</p>

<blockquote>
  <p>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</p>
</blockquote>

<p>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:</p>

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

<hr>

<p><a href="http://www.mathcs.duq.edu/~wimmer/" rel="noreferrer">Karl Wimmer</a> commented on the point raised by <a href="https://cstheory.stackexchange.com/a/38812/13319">Gustav Nordh</a> (reproduced with Karl's permission):</p>

<blockquote>
  <p>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.</p>
  
  <p>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.</p>
  
  <p>(Aside: this one-sided-ness is consistent with <a href="https://cstheory.stackexchange.com/a/38812/13319">Gustav’s example</a>
  above.)</p>
  
  <p>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.</p>
  
  <p>If I’m totally off-base here, please let me know!</p>
</blockquote>

<hr>

<p><em>From an anonymous user, in reaction to Karl's point:</em></p>

<blockquote>
  <p>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.</p>
</blockquote>

<hr>

<p>And the answer by Karl (which I reproduce again here):</p>

<blockquote>
  <p>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)$</p>
  
  <p>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?</p>
  
  <p>(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.)</p>
</blockquote>

<hr>

<p>(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.</p>

<p>Explanation how R works:</p>

<blockquote>
  <p>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)$$</p>
</blockquote>

CC BY-SA 3.0
2017-08-15T14:54:35.517Z
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.
Andrew Morgan
CC BY-SA 3.0
2017-08-15T16:03:03.490Z
@AndrewMorgan I updated the CW answer.
Clement C.
CC BY-SA 3.0
2017-08-15T23:43:15.867Z
@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.
idolvon
CC BY-SA 3.0
2017-08-17T17:02:24.573Z
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
vzn
CC BY-SA 3.0
2017-08-17T17:33:38.923Z
oh! further research you are also quoting replies from baez blog post which contains Wimmers reply etc https://johncarlosbaez.wordpress.com/2017/08/15/norbert-blum-on-p-versus-np/
vzn
CC BY-SA 3.0
2017-08-17T17:39:14.817Z
@vzn Karl actually sent these comments to me by enail, but yes, they are originally from there I think.
Clement C.
CC BY-SA 3.0
2017-08-15T14:38:04.403Z
2017-08-16T08:13:41.607Z
2017-08-16T08:13:41.607Z
Clement C.
<p>The correctness of the claimed proof is being discussed at Luca Trevisan's blog: <a href="https://lucatrevisan.wordpress.com/2017/08/15/on-norbert-blums-claimed-proof-that-p-does-not-equal-np/" rel="nofollow noreferrer">https://lucatrevisan.wordpress.com/2017/08/15/on-norbert-blums-claimed-proof-that-p-does-not-equal-np/</a></p>

<p>In particular "anon" posted the following relevant comment:</p>

<p>"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."</p>

<p>On a direct question from "Mikhail", Alexander Razborov confirms this (see Mikhail's post):
<strong>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.</strong> - A. Razborov</p>

<p>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.</p>

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

<blockquote>
  <p>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</p>
</blockquote>

CC BY-SA 3.0
2017-08-16T07:44:52.177Z
I posted this as an answer as I don't have privileges yet to post comments.
Gustav Nordh
CC BY-SA 3.0
2017-08-16T11:30:53.203Z
Note that Blum himself mentions that there is a polynomial size circuit for seperating k-cliques from comple (k-1)-partite graphs (section 5).
user60974
CC BY-SA 3.0
2017-08-16T11:41:06.690Z
On the surface of it, Theorem 5 is false for the (non-monotone) indicator function of k-cliques and the proof of Theorem 6 invokes Theorem 5.
user60974
CC BY-SA 3.0
2017-08-16T11:51:50.037Z
@user60974 Thanks, missed that!
Gustav Nordh
CC BY-SA 3.0
2017-08-16T12:24:03.610Z
However, I agree that the fact that Tardos has given a monotone boolean function which is 1 on k-cliques and 0 on complete (k-1)-partite graphs but is polynomial time computable seems to refute Blums paper.  Without looking at any proofs, Lemma 5 and Theorem 6 in Blums paper contradicts this result by Tardos.
user60974
CC BY-SA 3.0
2017-08-16T12:49:15.510Z
Unfortunately this seems to be the case.
Gustav Nordh
CC BY-SA 3.0
2017-08-16T13:38:16.810Z
@GustavNordh To be sure I understand the two comments above: without pinpointing exactly where the proof itself fails, invoking Tardos' result would imply that Blum's (Lemma 5+Theorem 6) cannot possibly be true?
Clement C.
CC BY-SA 3.0
2017-08-16T15:16:38.687Z
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).
Gustav Nordh
CC BY-SA 3.0
2017-08-17T00:29:44.120Z
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.
Clement C.
CC BY-SA 3.0
2017-08-17T18:14:40.890Z
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.
idolvon
CC BY-SA 3.0
2017-08-17T19:24:10.613Z
OK, so a Lovasz theta function is decreasing (i.e. of a complement is increasing) with adding an edge, so a good enough approximation of (theta>k) it is plausibly monotone, but I would still want to see the reference
idolvon
CC BY-SA 3.0
2017-08-17T23:39:45.037Z
Tardos' function is defined in her very short paper located here: http://www.cs.cornell.edu/~eva/Gap.Between.Monotone.NonMonotone.Circuit.Complexity.is.Exponential.pdf Moreover the properties of Tardos' function is discussed in detail in [S. Jukna, Boolean Function Complexity p. 272]
Gustav Nordh
CC BY-SA 3.0
2017-08-16T07:40:42.277Z
2017-08-31T05:40:31.633Z
2017-08-31T05:40:31.633Z
Gustav Nordh
<p>Gustav Nordh <a href="https://johncarlosbaez.wordpress.com/2017/08/15/norbert-blum-on-p-versus-np/#comment-97652" rel="noreferrer">commented on</a> by Theorem 5 (page 29). Specifically, the function</p>

<p>$$(x\lor y) \land (\lnot x \lor y) \land (x \lor \lnot y)$$</p>

<p>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$.</p>

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

<p>$$x\lor y \lor (x\land y)$$</p>

<p>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$.</p>

CC BY-SA 3.0
2017-08-15T23:15:44.837Z
It appears that DNF' for this formula is (x AND y) - form full DNF, cancel trivial terms, and apply absorption
idolvon
CC BY-SA 3.0
2017-08-16T01:05:03.813Z
@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.
kdog
CC BY-SA 3.0
2017-08-16T04:09:18.577Z
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.
idolvon
CC BY-SA 3.0
2017-08-16T04:45:47.127Z
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),$$
idolvon
CC BY-SA 3.0
2017-08-16T04:45:58.560Z
(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)$$
idolvon
CC BY-SA 3.0
2017-08-16T12:57:47.303Z
Yes, that does seem to be the intention of the paper, and that would explain the issue, thank you.
kdog
CC BY-SA 3.0
2017-08-15T16:31:48.343Z
2017-08-16T15:49:02.487Z
2017-08-16T15:49:02.487Z
kdog
<p>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 <a href="https://doi.org/10.1006/jcss.1999.1653" rel="noreferrer">membership comparable paper</a>? Or is the POLY function known to be NP-complete?</p>

CC BY-SA 3.0
2017-08-16T21:56:18.890Z
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.
Ravi Boppana
CC BY-SA 3.0
2017-08-17T13:43:42.287Z
Johnson's 1986 article predates the polynomial reconstruction techniques and list-decoding results of the 90s.
Lance Fortnow
CC BY-SA 3.0
2017-08-17T13:53:13.010Z
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.
Lance Fortnow
CC BY-SA 3.0
2017-08-17T20:07:41.713Z
Elementary question: how would resolving the complexity status of POLY, in either direction, affect Blum's argument?
Matt
CC BY-SA 3.0
2017-08-17T20:25:38.867Z
@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.
Clement C.
CC BY-SA 3.0
2017-08-18T09:03:30.280Z
@ClementC. So essentially is this a proof that $NP\not\subseteq P/poly$? I think this interesting Andreev's POLY function query may be suitable for Mathoverflow?
Turbo
CC BY-SA 3.0
2017-08-18T09:14:02.030Z
@ClementC. Lance Fortnow's argument is not that 'if it is in P, it must have polynomial circuit complexity' rather 'if it is in RP, it must have polynomial circuit complexity' since he uses randomness to choose edges. He employs the possible power of randomness.
Turbo
CC BY-SA 3.0
2017-08-18T09:21:24.007Z
@LanceFortnow I think it suffices to show Andreev's function is in RP.
Turbo
CC BY-SA 3.0
2017-08-18T13:27:30.270Z
I wouldn't worry about the randomness aspect, generally these algorithms can be derandomized. But as @AbhishekBhrushundi points out, the parameters probably don't work out so the point is moot.
Lance Fortnow
CC BY-SA 3.0
2017-08-16T11:38:36.813Z
2017-08-16T11:38:36.813Z
Lance Fortnow
<p>He has <a href="https://arxiv.org/abs/1708.03486v2" rel="noreferrer">updated his arXiv</a>  to say his proof is incorrect:</p>

<blockquote>
  <p>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.</p>
</blockquote>

CC BY-SA 3.0
2017-08-31T18:09:05.030Z
2017-08-31T18:09:05.030Z
user541686
<p>Lipton and Regan's blog <a href="https://rjlipton.wordpress.com/2017/08/17/on-the-edge-of-eclipses-and-pnp/#comment-83654" rel="noreferrer">here</a> has a nice high level discussion with an interesting comment on the proof structure. </p>

<p>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.</p>

CC BY-SA 3.0
2017-08-17T22:11:22.787Z
2017-08-17T22:11:22.787Z
kodlu
<p>Also, here:
<a href="https://www.quora.com/Whats-the-status-of-Norbert-Blums-claim-that-operatorname-P-neq-operatorname-NP" rel="nofollow noreferrer">https://www.quora.com/Whats-the-status-of-Norbert-Blums-claim-that-operatorname-P-neq-operatorname-NP</a></p>

<p>Quoting Alon Amit:</p>

<blockquote>
  <p>(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.</p>
</blockquote>

CC BY-SA 3.0
2017-08-16T13:36:37.747Z
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](https://rjlipton.wordpress.com/2017/04/30/a-great-solution/).
Clement C.
CC BY-SA 3.0
2017-08-16T14:08:11.197Z
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.
Jack
CC BY-SA 3.0
2017-08-16T13:27:14.697Z
2017-08-16T13:27:14.697Z
Jack
<p>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. </p>

<p>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.</p>

CC BY-SA 3.0
2017-08-18T14:11:11.280Z
nice/ relevant point; fyi razborovs "no go" thm is "on the method of approximations" (1989) http://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 https://en.wikipedia.org/wiki/Natural_proof
vzn
CC BY-SA 3.0
2017-08-19T02:25:03.597Z
downvoted because the content of this answer was already addressed in previous answers.
verifying
CC BY-SA 3.0
2017-08-17T11:36:41.797Z
2017-08-17T11:36:41.797Z
Skeptic
<p>Blum uses Razborov´s method of approximation to conclude that a function in $NP-c$ can´t be computed in $P$.</p>

<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. </p>

<p>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.</p>

<p>Some (may be all) functions are isomorphics (problems aren´t). </p>

<p>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. </p>

CC BY-SA 4.0
2017-08-19T15:26:15.070Z
2018-09-04T16:56:24.067Z
2018-09-04T16:56:24.067Z
Ixer
<p>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:</p>

<p><strong>The single error</strong> 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. </p>

<p>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:</p>

<p>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).</p>

<p>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.</p>

<p>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).</p>

<p>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)? </p>

<p>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.</p>

<p>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. </p>

<p>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. </p>

<p>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). </p>

<p><strong>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.</strong></p>

CC BY-SA 3.0
2017-08-18T16:14:47.297Z
seems to be same comment on RJL blog https://rjlipton.wordpress.com/2017/08/17/on-the-edge-of-eclipses-and-pnp/#comment-83680 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 http://www.sciencedirect.com/science/article/pii/0304397585902099
vzn
CC BY-SA 3.0
2017-08-19T01:56:45.743Z
@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.
Clement C.
CC BY-SA 3.0
2017-08-22T20:23:12.290Z
Just curious, has there been any sort of further public communication from Blum after uploading the paper to the arxiv?
Matt
CC BY-SA 3.0
2017-08-31T05:52:15.763Z
@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"
Gustav Nordh
CC BY-SA 3.0
2017-09-07T20:22:59.650Z
This answer has been confirmed as correct by Scott Aaronson, citing other (unnamed) reviewers: https://www.scottaaronson.com/blog/?p=3409
Jacob Brazeal
CC BY-SA 4.0
2024-03-13T13:24:43.693Z
For the record, the explanation by Blum about the error is here: https://theory.cs.uni-bonn.de/blum/PvsNP/mistake.pdf
Antoine Amarilli 'a3nm'
CC BY-SA 3.0
2017-08-18T12:05:50.377Z
2017-08-18T15:33:22.050Z
2017-08-18T15:33:22.050Z
idolvon
<p><a href="http://theory.cs.uni-bonn.de/info5/groups-en.html" rel="noreferrer">Norbert Blum</a> recently posted a 38-page <a href="https://arxiv.org/abs/1708.03486" rel="noreferrer">proof</a> that $P \ne NP$. Is it correct?</p>

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

<p><em>Note: the focus of this question text has changed over time. See question comments for details.</em></p>

CC BY-SA 4.0
2018-09-02T21:42:18.777Z
Comments are not for extended discussion; this conversation has been [moved to chat](https://chat.stackexchange.com/rooms/82635/discussion-on-question-by-warren-schudy-is-norbert-blums-2017-proof-that-p-ne).
Bjørn Kjos-Hanssen
<cc.complexity-theory><np-hardness><complexity-classes>
Is Norbert Blum's 2017 proof that $P \ne NP$ correct?
Warren Schudy
# Is Norbert Blum's 2017 proof that $P \ne NP$ correct?

(Asked by: username_0 on 2017-08-14)

[Norbert Blum](http://theory.cs.uni-bonn.de/info5/groups-en.html) recently posted a 38-page [proof](https://arxiv.org/abs/1708.03486) 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.*

**Tags:** cc.complexity-theory, np-hardness, complexity-classes
> **Comments:**
> **username_1**: Comments are not for extended discussion; this conversation has been [moved to chat](https://chat.stackexchange.com/rooms/82635/discussion-on-question-by-warren-schudy-is-norbert-blums-2017-proof-that-p-ne).  

---

## 11 answers

### Answer by username_4 on 2017-08-18. Score: 103 | Accepted answer

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.**

> **Comments:**
> **username_6**: seems to be same comment on RJL blog https://rjlipton.wordpress.com/2017/08/17/on-the-edge-of-eclipses-and-pnp/#comment-83680 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 http://www.sciencedirect.com/science/article/pii/0304397585902099  
> **username_7**: @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.  
> **username_14**: Just curious, has there been any sort of further public communication from Blum after uploading the paper to the arxiv?  
> **username_9**: @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"  
> **username_22**: This answer has been confirmed as correct by Scott Aaronson, citing other (unnamed) reviewers: https://www.scottaaronson.com/blog/?p=3409  
> **username_23**: For the record, the explanation by Blum about the error is here: https://theory.cs.uni-bonn.de/blum/PvsNP/mistake.pdf  

---

### Answer by username_2 on 2017-08-17. Score: 94

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.**

> **Comments:**
> **username_3**: It would be great if you could elaborate on this. Is Tardos' function known to be in P?  
> **username_4**: 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?  
> **username_5**: @idolvon You mean this: http://www.cs.cornell.edu/~eva/Gap.Between.Monotone.NonMonotone.Circuit.Complexity.is.Exponential.pdf It explicitly states that the function φ is poly-time computable monotone function  
> **username_4**: 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.  
> **username_5**: @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).  
> **username_6**: great to hear from virtuoso/ pioneer/ grandmaster razborov himself even 2ndhand. but even grandmasters can have blind spots... if anyone tries to go this direction they need to study berkowitz 1982 who showed superpolynomial center slice functions lower bounds for monotone circuits are _sufficient_ to separate P vs NP. both razborov/ blum apparently have never cited berkowitz! serious researchers maybe _need to give_ up on looking at 2 slices T0, T1 and focus on a _single center one!_ Rossman 2009 points the way where to look http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.156.5526  

---

### Answer by username_7 on 2017-08-15. Score: 41

*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](https://people.eecs.berkeley.edu/~luca/) from a [public Facebook post](https://www.facebook.com/shachar.lovett/posts/10155282027901321) (08/14/2017), replying to a question about this paper asked by [Shachar Lovett](http://cseweb.ucsd.edu/~slovett/):

> 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](http://www.mathcs.duq.edu/~wimmer/) commented on the point raised by [Gustav Nordh](https://cstheory.stackexchange.com/a/38812/13319) (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](https://cstheory.stackexchange.com/a/38812/13319)
> 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)$$

> **Comments:**
> **username_8**: 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.  
> **username_7**: @AndrewMorgan I updated the CW answer.  
> **username_4**: @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.  
> **username_6**: 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  
> **username_6**: oh! further research you are also quoting replies from baez blog post which contains Wimmers reply etc https://johncarlosbaez.wordpress.com/2017/08/15/norbert-blum-on-p-versus-np/  
> **username_7**: @vzn Karl actually sent these comments to me by enail, but yes, they are originally from there I think.  

---

### Answer by username_9 on 2017-08-16. Score: 35

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

> **Comments:**
> **username_9**: I posted this as an answer as I don't have privileges yet to post comments.  
> **username_10**: Note that Blum himself mentions that there is a polynomial size circuit for seperating k-cliques from comple (k-1)-partite graphs (section 5).  
> **username_10**: On the surface of it, Theorem 5 is false for the (non-monotone) indicator function of k-cliques and the proof of Theorem 6 invokes Theorem 5.  
> **username_9**: @user60974 Thanks, missed that!  
> **username_10**: However, I agree that the fact that Tardos has given a monotone boolean function which is 1 on k-cliques and 0 on complete (k-1)-partite graphs but is polynomial time computable seems to refute Blums paper.  Without looking at any proofs, Lemma 5 and Theorem 6 in Blums paper contradicts this result by Tardos.  
> **username_9**: Unfortunately this seems to be the case.  
> **username_7**: @GustavNordh To be sure I understand the two comments above: without pinpointing exactly where the proof itself fails, invoking Tardos' result would imply that Blum's (Lemma 5+Theorem 6) cannot possibly be true?  
> **username_9**: 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).  
> **username_7**: 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.  
> **username_4**: 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.  
> **username_4**: OK, so a Lovasz theta function is decreasing (i.e. of a complement is increasing) with adding an edge, so a good enough approximation of (theta>k) it is plausibly monotone, but I would still want to see the reference  
> **username_9**: Tardos' function is defined in her very short paper located here: http://www.cs.cornell.edu/~eva/Gap.Between.Monotone.NonMonotone.Circuit.Complexity.is.Exponential.pdf Moreover the properties of Tardos' function is discussed in detail in [S. Jukna, Boolean Function Complexity p. 272]  

---

### Answer by username_11 on 2017-08-15. Score: 24

Gustav Nordh [commented on](https://johncarlosbaez.wordpress.com/2017/08/15/norbert-blum-on-p-versus-np/#comment-97652) 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$.

> **Comments:**
> **username_4**: It appears that DNF' for this formula is (x AND y) - form full DNF, cancel trivial terms, and apply absorption  
> **username_11**: @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.  
> **username_4**: 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.  
> **username_4**: 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),$$  
> **username_4**: (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)$$  
> **username_11**: Yes, that does seem to be the intention of the paper, and that would explain the issue, thank you.  

---

### Answer by username_12 on 2017-08-16. Score: 17

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](https://doi.org/10.1006/jcss.1999.1653)? Or is the POLY function known to be NP-complete?

> **Comments:**
> **username_13**: 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.  
> **username_12**: Johnson's 1986 article predates the polynomial reconstruction techniques and list-decoding results of the 90s.  
> **username_12**: 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.  
> **username_14**: Elementary question: how would resolving the complexity status of POLY, in either direction, affect Blum's argument?  
> **username_7**: @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.  
> **username_15**: @ClementC. So essentially is this a proof that $NP\not\subseteq P/poly$? I think this interesting Andreev's POLY function query may be suitable for Mathoverflow?  
> **username_15**: @ClementC. Lance Fortnow's argument is not that 'if it is in P, it must have polynomial circuit complexity' rather 'if it is in RP, it must have polynomial circuit complexity' since he uses randomness to choose edges. He employs the possible power of randomness.  
> **username_15**: @LanceFortnow I think it suffices to show Andreev's function is in RP.  
> **username_12**: I wouldn't worry about the randomness aspect, generally these algorithms can be derandomized. But as @AbhishekBhrushundi points out, the parameters probably don't work out so the point is moot.  

---

### Answer by username_16 on 2017-08-31. Score: 15

He has [updated his arXiv](https://arxiv.org/abs/1708.03486v2) 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.


---

### Answer by username_17 on 2017-08-17. Score: 9

Lipton and Regan's blog [here](https://rjlipton.wordpress.com/2017/08/17/on-the-edge-of-eclipses-and-pnp/#comment-83654) 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.


---

### Answer by username_18 on 2017-08-16. Score: 3

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.

> **Comments:**
> **username_7**: 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](https://rjlipton.wordpress.com/2017/04/30/a-great-solution/).  
> **username_18**: 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.  

---

### Answer by username_19 on 2017-08-17. Score: 2

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.

> **Comments:**
> **username_6**: nice/ relevant point; fyi razborovs "no go" thm is "on the method of approximations" (1989) http://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 https://en.wikipedia.org/wiki/Natural_proof  
> **username_20**: downvoted because the content of this answer was already addressed in previous answers.  

---

### Answer by username_21 on 2017-08-19. Score: 0

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.


---

