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

Re:On Norbert Blum’s claimed proof that P does not equal NP by naturalgradient on Wednesday August 16, 2017 @01:20PM (#15029288)

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

[ Parent | on HN ]

Re:On Norbert Blum’s claimed proof that P does not equal NP by JaguarCat on Friday August 18, 2017 @11:48AM (#15047212)

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

[ Parent | on HN ]

Re:On Norbert Blum’s claimed proof that P does not equal NP by crb002 on Wednesday August 16, 2017 @01:24PM (#15029325)

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.

[ Parent | on HN ]

Re:On Norbert Blum’s claimed proof that P does not equal NP by Ar-Curunir on Wednesday August 16, 2017 @04:54PM (#15031295)

Any clarification on how you expect such arguments to be used? Otherwise your claims are completely out of left field, because most approaches are not anything along those lines.

[ Parent | on HN ]

Re:On Norbert Blum’s claimed proof that P does not equal NP by sn41 on Thursday August 17, 2017 @12:34AM (#15033834)

Kolmogorov had an outline of an attempt using Kolmogorov Complexity to settle P vs NP. I do not unfortunately recall the crux of the argument. This was formulated in the 1970s, and has not been followed up as far as I know. On the other hand, given Baker-Gill-Solovay and the Natural Proof barriers, no proof settling the question is expected to be easy.

[ Parent | on HN ]