12 ms·
Blum: “The proof is wrong. I shall elaborate precisely what the mistake is.”
- avs733 9y agoThank you for the title update. I know there was a pool on how long till it was disproved. Who had 19days?
- technofire 9y agoIt was known long before 19 days, actually within a week of publication: https://cstheory.stackexchange.com/questions/38803/is-norbert-blums-2017-proof-that-p-ne-np-correct/38823 https://cstheory.stackexchange.com/questions/38803/is-norber...
- viksit 9y agoDoes anyone know who wrote that answer?
- chx 9y agoCheck https://cstheory.stackexchange.com/a/38832/5630 https://cstheory.stackexchange.com/a/38832/5630 Alexander Razborov was the first to prove it wrong by providing a counterexample. He got a Nevanlinna Prize in 1990 for a result in this field, it's not a surprise at all he was the one.
- avs733 9y agoThank you! That's what I get for falling behind on the theoretical computer science stack exchange.
- herodotus 9y agoIs the comment that "the proof is wrong" from the author himself?
- Etheryte 9y agoYes, both the article ("A Solution of the P versus NP Problem") and the comment on it ("The proof is wrong") are written by Blum. It's both very nice and honorable that the author is pointing out his own errors publicly.
- molyss 9y agoIn retrospect, I think the initial abstract of the paper ("Berg and Ulfberg and Amano and Maruoka have used CNF-DNF-approximators to prove exponential lower bounds for the monotone network complexity of the clique function and of Andreev's function. We show that these approximators can be used to prove the same lower bound for their non-monotone network complexity. This implies P not equal NP.") was also a way to have as many people as possible double check the proof, due to the very strong result of the paper. In other words, he might not have been building up the hype but instead was making sure he wouldn't have to retract a paper with a (more or less) obvious mistake in it. That's how science should be done rather than behind closed doors !
- quantdev 9y agoI don't understand what you're trying to say. How would his abstract be different if he wasn't trying to get as many people to look at it? Many results in math establish a famous theorem by proving something more abstract that "easily" implies the famous result, like with Fermat's Last Theorem.
- colanderman 9y agoPerhaps by leaving off the last sentence, "this implies P not equal NP", and changing the title. That sentence does not change the meaning of the paper; it just adds an eye-catching (and already accepted as true) implication.
- quantdev 9y agoI suppose, though it would be very strange and disingenuous to leave off the most important implication.
- willvarfar 9y agoThe homepage Blum is referring to is presumably http://theory.cs.uni-bonn.de/blum/blum.var http://theory.cs.uni-bonn.de/blum/blum.var but I can't find an explanation of the flaw there yet.
- y7 9y agoIn his comment from yesterday, he wrote that he needed some time. I guess it will be up somewhere next month.
- technofire 9y agoThe flaw is shown here: https://cstheory.stackexchange.com/questions/38803/is-norbert-blums-2017-proof-that-p-ne-np-correct/38823 https://cstheory.stackexchange.com/questions/38803/is-norber...
- komali2 9y agoWelp looks like I have a whole new set of things to learn before I can read a thing :P
- isuckatcoding 9y agoThis sounds like a foreign language to me.
- sova 9y agoWhat a fantastic person to point out such a subtlety once it has come to light. Easily steer your fellow scientists right!
- xrange 9y agoHere's an utterly trivial question. Do most people working on computational problems like this consider themselves mathematicians or scientists?
- jdoliner 9y agoMathematicians, despite the fact that the field is called "Computer Science"
- sova 9y agoDijkstra say Computational Scientist
- _kst_ 9y agoDijkstra is alleged to have said: "Computer science is no more about computers than astronomy is about telescopes." but that's disputed. https://en.wikiquote.org/wiki/Computer_science#Disputed https://en.wikiquote.org/wiki/Computer_science#Disputed
- icebraining 9y agoHe has said something to more or less the same effect: it was firmly implanted in people’s minds that computing science is about machines and their peripheral equipment. Quod non [Latin: "Which is not true"]. We now know that electronic technology has no more to contribute to computing than the physical equipment. We now know that programmable computer is no more and no less than an extremely handy device for realizing any conceivable mechanism without changing a single wire, and that the core challenge for computing science is hence a conceptual one, viz., what (abstract) mechanisms we can conceive without getting lost in the complexities of our own making.
- DrBazza 9y agoAnd this what science is about. I'm wrong and I'll say so. I've been proved wrong, because I was wrong.
- dekhn 9y agomath, not science
- pwdisswordfish 9y agoPedantic distinction that exists only in English.
- quirkot 9y agoThis is correct. In another language we'd refer to the distinction with a different word
- wsy 9y agoIn German, "Wissenschaft" includes all kinds of academic knowledge production, regardless if mathematics, natural sciences ("Naturwissenschaften"), humanities ("Geisteswissenschaften"), or engineering ("Ingenieurwissenschaften"). So, when translating the remark to German, it would be difficult to come up with a "different word" for the distinction. For the collectors of useless knowledge: for a while, there was an attempt to establish the term "Strukturwissenschaften" (science of structures), covering mathematics, computer science, and system theory. But that term did not really stick.
- lmkg 9y agoThe distinction is significant, despite their relationship they're from totally different universes. Science is empirical: truth is validated by observation of the real world. Math is logical: truth is validated purely by internal consistency.
- chestervonwinch 9y ago
- deepnotderp 9y agoAwesome, this is science and math working as it should be, kudos to Blum!
- exikyut 9y agoFor anyone dense like me: - The author has uploaded a [v2] with file size 0 bytes (see bottom of page); this constitutes retraction of the publication - [v2] has a comment, shown approximately partway down the page, which is what this post's subject cites You can click the [v1] link to get a PDF link to the now-retracted information. I really like arXiv's versioned publishing.
- mastazi 9y agoThat's why when you share Arxiv links you should never ever share direct links to the pdf. E.g. If someone shared v1 before the author retracted, by visiting that link (even today) you would know nothing about what happened.
- foota 9y agoHe sounds crushed, I hope he's doing okay. Must be hard to have something be wrong after working on it for what I imagine was a very long time.