On Norbert Blum’s claimed proof that P does not equal NP

[spaceseaman]

> I am confident that by the end of the week we will hear substantive comments on the technical claims in the paper.

I am amazed by the speed with which mathematicians are able to quickly congregate and debate such things like this. It makes me excited to enter a graduate program knowing that people take academia so seriously. Their love and devotion to purely intellectual pursuits should really be appreciated every once in awhile.

[astrodust]

It's not like nobody's ever tried this before. There's many experts that have probably committed years if not more to understanding this and would be in a very good position to evaluate this paper due to their depth of knowledge.

[kusmi]

In about 3-4 years you'll come to realize it's about ego.

[solomatov]

> Their love and devotion to purely intellectual pursuits should really be appreciated every once in awhile.

It's not purely intellectual pursuit. I am sure, eventually, there will be some applications of it.

[naturalgradient]

Some interesting ongoing discussion (last post an hour ago):

https://cstheory.stackexchange.com/questions/38803/where-is-...

In particular someone claimed to have found a flaw (which I can not comment on, not a complexity theory person):

'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)'

[JaguarCat]

As far, as I understand Blum's paper, he doesn't talk about general non-monotone networks, but rather about "standard networks", where all 'not' gates are moved to the front: "The resulting network is a so-called standard network where only input variables are negated."

Could it be, that Tardos' function has exponential monotone network complexity, exponential standard network complexity (with inverters allowed at front), but polygonal complexity in general networks (with not gates/inverters also allowed in the middle)?

[crb002]

I'm 90% sure the first paper proving P!=NP will either use a Kolmogorov complexity argument, or an exact enumeration involving a semigroup problem that is exponential.

[weinzierl]

Scott Aaronson is confident that it will be refuted by the end of the week:

> I’d again bet $200,000 that the paper won’t stand [...] and if the thing hasn’t been refuted by the end of the week, you can come back and tell me I was a closed-minded fool.

http://www.scottaaronson.com/blog/?p=3389

On the other hand, his original post contained an short explanation (one or two sentences) what he believed to be a flaw in the paper, which he has removed since then.

[naturalgradient]

FWIW,

I think Aaronson's dismissive attitude is unbecoming and disrespectful amongst colleagues.

'Unrelated Update: To everyone who keeps asking me about the “new” P≠NP proof: I’d again bet $200,000 that the paper won’t stand, except that the last time I tried that, it didn’t achieve its purpose, which was to get people to stop asking me about it. So: please stop asking, and if the thing hasn’t been refuted by the end of the week, you can come back and tell me I was a closed-minded fool.'

Quick-copy pasting a Facebook comment as reason not to want to deal with it, betting a large sum of money almost tauntingly is not good scholarship.

A serious researcher made a serious effort to solve a problem. Say you have not verified it and don't want to comment.

It almost seems like he does not want P/NP to be proven because he has made a reputation by becoming an authority on dismissing attempts.

[deathWasp271]

Relevant XKCD:

https://xkcd.com/955/

[brudgers]

Knuth on why he believes P = NP and what it means [see question 17]:

http://www.informit.com/articles/article.aspx?p=2213858

[crsv]

I read these things and I wish I could understand it with a cursory knowledge of mathematical theory, but alas, I'm left longing for understanding, because it seems like a really interesting debate.

[crb002]

I've been convinced P!=NP ever since I started studying semigroup lower bounds. Even black box group membership is exponential in the largest prime less than or equal to N. https://oeis.org/A186202

[jmcgough]

P!=NP seems to be the general sentiment, though we're still waiting on the proof :)

[padobson]

Yeah, proving it is not going to be much of a game changer. Most everyone already assumes it's true.

But if someone were to prove the opposite, the entire technology world would shift dramatically, so it will certainly help to have a proof for this.

[maweki]

I could be convinced that P=NP, but that would also mean that Co-NP=P and I just couldn't wrap my mind around that one.

Co-NP just seems so much harder than NP.

[danbruc]

I have been convinced that P==NP since my first exposure to the topic in university. There are NP complete problems where I can really not imagine how they could be solved quickly, but vertex three coloring just looks so doable to me by some informal intuitive arguments. In another life I would devote my life to fleshing out the argument and proving P==NP. Or at least learn where my intuitive argument fails.