7 ms·

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

139 points by cschmidt 9y ago

naturalgradient 9y ago
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'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 https://oeis.org/A186202
- jmcgough 9y ago
  P!=NP seems to be the general sentiment, though we're still waiting on the proof :)
  - tachyonbeam 9y ago
    I share the same sentiment, but I think it could be that P!=NP is an unprovable statement. Could be that there's something fundamental about the nature of computing which makes it impossible to prove or disprove it.
    - sacheendra 9y ago
      Maybe that could be a thing to prove. Is it possible to prove that something is not provable?
      - jlebar 9y ago
        See http://www.scottaaronson.com/papers/indep.ps http://www.scottaaronson.com/papers/indep.ps
      - emmab 9y ago
        > Is it possible to prove that something is not provable? It's possible to prove that something is not provable within some axiom set. See: https://en.wikipedia.org/wiki/List_of_statements_independent_of_ZFC https://en.wikipedia.org/wiki/List_of_statements_independent...
      - infogulch 9y ago
        In general yes. [1] I don't know about PvNP [1]: https://math.stackexchange.com/questions/2027182/how-do-we-prove-that-something-is-unprovable https://math.stackexchange.com/questions/2027182/how-do-we-p...
spaceseaman 9y ago
> 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 9y ago
  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.
- solomatov 9y ago
  > 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.
  - OtterCoder 9y ago
    > It's not purely intellectual pursuit. I feel like you don't really understand theoretical mathematicians. Application is a side effect of the highest maths, not a goal of its practitioners.
- kusmi 9y ago
  In about 3-4 years you'll come to realize it's about ego.
weinzierl 9y ago
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 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.
- deleted 9y ago
  [deleted]
- deleted 9y ago
  [deleted]
- naturalgradient 9y ago
  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.
  - CJefferson 9y ago
    No, it's because one could spend a hundred lifetimes showing incorrect P vs NP proofs. Either he is right, or if the author is convinced of the disrespect they can $200,000. Most people who publish proofs don't seem to make any attempt to get their work reviewed before putting it out onto the open internet. That's of course their choice, but then you have to expect people to tell you where you have wrong, bluntly. It's a huge waste of everyone's time who then reads the proof.
deleted 9y ago
[deleted]
brudgers 9y ago
Knuth on why he believes P = NP and what it means [see question 17]: http://www.informit.com/articles/article.aspx?p=2213858 http://www.informit.com/articles/article.aspx?p=2213858
crsv 9y ago
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.

139 points by cschmidt 9y ago

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'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 https://oeis.org/A186202

jmcgough 9y ago
P!=NP seems to be the general sentiment, though we're still waiting on the proof :)
- tachyonbeam 9y ago
  I share the same sentiment, but I think it could be that P!=NP is an unprovable statement. Could be that there's something fundamental about the nature of computing which makes it impossible to prove or disprove it.
  - sacheendra 9y ago
    Maybe that could be a thing to prove. Is it possible to prove that something is not provable?
    - jlebar 9y ago
      See http://www.scottaaronson.com/papers/indep.ps http://www.scottaaronson.com/papers/indep.ps
    - emmab 9y ago
      > Is it possible to prove that something is not provable? It's possible to prove that something is not provable within some axiom set. See: https://en.wikipedia.org/wiki/List_of_statements_independent_of_ZFC https://en.wikipedia.org/wiki/List_of_statements_independent...
    - infogulch 9y ago
      In general yes. [1] I don't know about PvNP [1]: https://math.stackexchange.com/questions/2027182/how-do-we-prove-that-something-is-unprovable https://math.stackexchange.com/questions/2027182/how-do-we-p...

spaceseaman 9y ago

> 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 9y ago
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.
solomatov 9y ago
> 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.
- OtterCoder 9y ago
  > It's not purely intellectual pursuit. I feel like you don't really understand theoretical mathematicians. Application is a side effect of the highest maths, not a goal of its practitioners.
kusmi 9y ago
In about 3-4 years you'll come to realize it's about ego.

weinzierl 9y ago

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

deleted 9y ago
[deleted]
deleted 9y ago
[deleted]
naturalgradient 9y ago
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.
- CJefferson 9y ago
  No, it's because one could spend a hundred lifetimes showing incorrect P vs NP proofs. Either he is right, or if the author is convinced of the disrespect they can $200,000. Most people who publish proofs don't seem to make any attempt to get their work reviewed before putting it out onto the open internet. That's of course their choice, but then you have to expect people to tell you where you have wrong, bluntly. It's a huge waste of everyone's time who then reads the proof.

deleted 9y ago

[deleted]

brudgers 9y ago

Knuth on why he believes P = NP and what it means [see question 17]: http://www.informit.com/articles/article.aspx?p=2213858 http://www.informit.com/articles/article.aspx?p=2213858

crsv 9y ago

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.