Comment by naturalgradient | Hacker News Reader

Comment by naturalgradient | Hacker News Reader

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

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

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.

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.

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.

Reply on news.ycombinator.com