3 ms·

Some interesting ongoing discussion (last post an hour ago): https://cstheory.stackexchange.com/questions/38803/where-is-norbert-blums-2017-proof-that-p-ne-np-

Some interesting ongoing discussion (last post an hour ago): https://cstheory.stackexchange.com/questions/38803/where-is-norbert-blums-2017-proof-that-p-ne-np-being-discussed#comment88798_38817 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)'

crb002 9y ago
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.
- Ar-Curunir 9y ago
  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.
- sn41 9y ago
  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.
JaguarCat 9y ago
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 9y ago

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.

Ar-Curunir 9y ago
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.
sn41 9y ago
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.

JaguarCat 9y ago

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