Blum: “The proof is wrong. I shall elaborate precisely what the mistake is.” 258 points by chx on Aug 31, 2017 | hide | past | favorite | 78 comments

 And this what science is about. I'm wrong and I'll say so. I've been proved wrong, because I was wrong.
 math, not science
 They both share the view that explanations/hypotheses can either be retained or rejected (and better explanations can retained).Math is unique in that the standard of proof is more comprehensive and the domain is bounded but this is a good example of someone employing the scientific method and exhibiting good scientific community values.
 No, mathematics works completely different than science. In both math and science, you do some observations, and then formulate theory that explain some of these observations. However, in science, you then design experiments and predict the results based on your theory, taking care to ensure that the experiments distinguish between the reality in which your theory holds, and the one where it doesn't.In math you might also do that as a sanity check, but that's not the point. In math, the point is to actually _prove_ your theory to be correct, something which is absolutely impossible to do in science, where you can only prove theory to be _wrong_.
 I like to think of it in terms of classical vs. constructive logic—the former is concerned with truth and falsehood, the latter with provability. In mathematics you can show that some hypothesis is true or false. In science you can only demonstrate that you have been unable to find an example of anything inconsistent with your hypothesis; that is, in the real world we don’t have the law of the excluded middle: ¬¬P is not the same as P.This also means that mathematics lets us talk about universal properties ∀x∈S.P(x) (“for all x in S, P is true of x”), but science really only gives you existential properties ∃x∈S.P(x) (“there is some x in S for which P is true of x”). The scientific method is based on the idea that enough statements of the form ¬K∃x∈S.¬P(x) (“it is not known that there is an x in S for which P is not true of x”) resulting from a large number of convincing experiments can serve as evidence of ¬∃x∈S.¬P(x) (“there is no x in S for which P is not true of x”) which gives us an approximation of ∀x∈S.P(x).
 >taking care to ensure that the experiments distinguish between the reality in which your theory holds, and the one where it doesn't.I get the impression that you're thinking of specific domains within science. Many theories are contextualized within something (e.g a theory of why there's lightning might be more domain specific than a theory of electromagnetism).I don't disagree that things are proved within mathematical systems and scientific claims / hypotheses are categorically different (and weaker, I suppose).But the author made a claim, discovered an error in their claim, and alerted the community to his mistake and signaled their intention to address it. That's not behavior that's exclusive to mathematics. Many scientists have made claims that they think the evidence supports, and then they realize that something wasn't correct, and they make the correction.Cartographers / mariners used to think that California was an island: https://en.wikipedia.org/wiki/Island_of_CaliforniaThey had solid evidence to think that's the case but then eventually they realized the mistake and they've corrected it.
 > They had solid evidence to think that's the caseWhy do you say this? It is not supported by the link you provide.
 You can't prove a theory wrong in science either. All you can do is to collect evidence that pushes you in one direction or the other.
 No, you can prove things wrong. In fact, a lot of science is in making sure that your claims are falsifiable.E.g, "the moon is made of cheese". cf. Bertrand Russell's teapot.
 We can't prove that wrong. We can just say it's almost certainly wrong given the body of evidence against it. It's distinctly possible that every single measurement and observation of the moon that observed it to not be made of cheese was mistaken for one reason or another, however.
 Ok, but then you're so far into pedantics that I'd suggest that you can't mathematically prove anything either, because you're using your brain to do so, which might be suffering from some flaw that stops you from realising that actually 1+1=3.
 That is only as pedantic as it is pedantic to say that science can't prove things right. There is no fundamental quality that makes a statement "positive" or "negative", so "proving X wrong" is always "proving ⌐X right". It's possible to be very precise about what we mean when we talk about evidence and logic, so coming up with these wishy-washy principles like "science can only prove things wrong; oh, you know what I mean" just confuses things.As for applying that to math, yes that's true to some extent. And on rare occasion, mathematical proofs are found to have flaws in them years after they have become commonly accepted. I think there's an important distinction to be made, though, between the certainty of deductive reasoning, and the uncertainty of deductive reasoning as interpreted by humans.
 If this is true then you can also prove things right: "the Moon is not made of cheese".
 I think everybody replying to my original comment ("math, not science") misunderstood what I meant. It's my fault, I was ambiguous.The person I replied to said "this is how science works". I replied "math, not science", meaning in this case, it was an example of how math works (self-correcting through review). But that's also how science works.I didn't mean to imply there were huge differences in the ontology of math and science, as practiced, although I found the subsequent discussion of the differences in their pursuits stimulating.I see less difference in math and science than most, probably due to the influence of "The Unreasonable Effectiveness of Mathematics in the Natural Sciences" iin which Wigner, one of the biggest players in quantum mechanics, points out that mathematical models/theories of physical systems often have unexpected extrapolative predictive ability, suggesting some relationship between math and physics (I believe some people would say that the universe has an underlying mathematical structure). https://www.dartmouth.edu/~matc/MathDrama/reading/Wigner.htm...
 Maths has proof. Science only has models that fit evidence collected so far
 How do you check a (human-created) math proof for correctness? By comparing it to evidence collected so far.If human-performed math were not a science, a retraction would never happen.
 > How do you check a (human-created) math proof for correctness? By comparing it to evidence collected so far.I don't understand this. You don't check a math proof against evidence, you check it for the correctness of the logical deductions from the axioms to the conclusions.Here's a proof that there are infinitely many primes:Take any finite collection of primes. Multiply them all together, and add one, giving a number X. Let P be the smallest prime that divides X (note that P might equal X). P cannot be in the original collection, so we have created a new prime. Therefore any finite collection of primes is incomplete, and so the collection of all primes must be infinite.Suppose I want to check that for correctness. No amount of evidence will show that it's correct, so I really don't know what you are saying. Perhaps you could expand on your thoughts using this as a specific example.
 No need to be pedantic as the comment you're responding to is not really referring to something particular to mathematics or natural sciences. And even if it did, whether or not maths is a science is a philosophical issue, not an invariable truth.
 Math is a science, just not an empirical science. It is a formal science.
 Not in the general sense that people use. Everything is a "science" just like everything is a "philosophy".In general day to day usage, science = natural/empirical science.
 > math, not science While true, it is an artefact of the usage of the term science in English.For example, theoretical computer science is no science according to that distinction between math and science.
 TCS is indeed mathematics, and not science.
 yes, CS is misnamed.
 I'll probably get lambasted with all the pedants coming out, but I chuckled when someone pointed out that most majors in college with the word science in them aren't really science i.e. Political Science, Computer Science, Sports Science, contrasted with i.e. Physics, Chemistry, etc.
 In Britain "political science" is strictly the process of applying (social) scientific approaches to the study of politics, with the rest of the discipline simply called "politics".Nobody trusts the political scientists, sadly. There are too many bloody variables and collecting good enough data to build cumulative models is hard. We persevere, though.
 What do they do for reproducibility?I'm pretty sure those types of things, such as social sciences, can be tested and reproduced, but I'd imagine there are ethical concerns.How do you reproduce Hitler's affect on politics and not end up on the receiving end of a tribunal in Hague?
 The same way you reproduce things in astrophysics or epidemiology: natural experiments.
 Got a good example I can look up?
 CS as practiced today contains elements of math, engineering, and the sciences (though rarely at the same time). I have a bit on this you might find interesting: http://bowaggoner.com/whatiscomputerscience.html#medium
 I'm not seeing any "science" in CS. I work at a company based on CS, I have a PhD in a quantitative physical field, and I don't really CS as being science. It's theoretical and applied math that happens to be executed on computers.
 I was always told that math is the most exact science.
 Formal Science?
 Pedantic distinction that exists only in English.
 The 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.
 The idea that the domain of science is restricted to falsifiable theories, and is therefore fundamentally empirical, dates only to the early part of the twentieth century. Since the Enlightenment, and also in the much older Western classical tradition, the term science (and its closest translations in Greek, Latin, German, French, and many other languages) has referred much more broadly than that restriction permits, to all fields of knowledge established in a rigorous manner, whether deductive or inductive.It's in that sense that Gauss crowned mathematics the "Königin der Wissenschaften," the Queen of the Sciences. And indeed in German the term Wissenschaft in ordinary usage still includes mathematics, referring to all knowledge amenable to investigation (as opposed to received knoweldge) [0]. The terms for science in many other Western languages also retain this broader meaning to a greater extent that does contemporary English, and the same is true in many non-Western cultures as well.The problem here is mainly a terminological one: in English we've found it useful to have a word that refers specifically to the Popperian notion of what counts as science (mainly, I think, to gain the power easily to distinguish "scientific" ideas from "non-scientific" bunk), but we haven't come up with a new term for the older, broader meaning of science as rigorously establishable knoweldge.I should also point out that Popperian science involves plenty of deductive reasoning—we call it theory—so while it is true that Popper's notion of science requires empiricism, it is not correct to identify it with the distinction between empirical and deductive reasoning. At the same time, the practice of mathematics certainly does involve empirical reasoning, often resulting in a conjecture whose truth is subsequently subjected to rigorous deductive arguments.(There is a section in the English Wikipedia article on mathematics that discusses this a bit more [1].)
 Yea well, that's just like, if you're a mathematical formalist, man.edit: I was merely pointing out that the parent's comment was an opinion based the branch of mathematical philosophy that the commenter appears to subscribe. I thought I'd add some humor by wrapping it in a Big Lebowski reference. And now I've explained away any attempt at humor ...
 Interesting. I'd like to learn more about this. Any pointers to how other languages and cultures don't distinguish between math and science? Does it apply to other things like the difference between induction and deduction as well?
 In Italy math is considered generally part of science. In fact here at the universities math is part of "Mathematical, Physical and Natural Sciences Faculty" (roughly translated).I am a bit surprised of the distinction; the term science comes from latin "scientia" which roughly means knowledge, so at least historically it was correct to consider math a science. Maybe it is a more recent (or just English) thing ?
 In Polish the word for science is "nauka" (noun from verb nauczyć = to finish learning/teaching), and it also covers math. People still obviously understand the differences and there are more specialized (almost never used [1]) terms like nauka matematyczna and nauka empiryczna (doświadczalna), we just don't see the reason to specifically say "science other than math" very often, so unless you're talking about philosophy of science you'll just say nauka and be done with it.It's like when you're talking about batteries in Tesla you don't specify they are reachargeable every time you use the word batteries.I used this example, because the same difference in language works the other way for batteries. English has batteries (unsepcified) and rechargeable or non-rechargeable batteries. Polish has baterie (always non-rechargeable), and akumulatory (always rechargeable), and no general word for both, so you always specify which ones these are.[1] Much more common distinction is "nauki ścisłe" (exact sciences - math, physics, etc) vs the rest.As for induction and deduction I understand the terms and they exist in Polish (indukcja and dedukcja), but I don't see the point. Both are used in math and in sciences?
 There are no pointers because just about every culture distinguishes between empirical and logical truths. I'm not sure if he's just being cute, but there's a very clear philosophical difference between math and science. This is not a pedantic distinction.(Someone from reddit that "loves science" might think so, though.)
 > just about every culture distinguishes between empirical and logical truthsActually, having this distinction is quite young even in our own western culture: depending what exactly you mean, ~300 years (Kants distinction between "Synthetisches Urteil" vs. "Analytisches Urteil"), or 150 years(Gottlob Frege's 'invention' of formal logic). And modern philosophy of science is already doubting it again (e.g., W.V. Quine).
 Nope. Descartes, Leibniz and Spinoza were rationalists. Hume, Berkeley, Locke were empiricists. This distinction wasn't formalized until relatively recently, but the intuition is very old.In antiquity, Pythagoras and Plato fall in the former camp; Serapion of Alexandria and Philinus of Cos fall in the latter.
 I have no expertise in ancient philosophy, so can't comment on these philosophers.Is 'cogito ergo sum' a logical or an empirical truth? For Descartes it was a logical truth (undoubtably true). However, from the point of view of Hume, it must be viewed as empirical truth, because it is based on an empirical observation. So if even philosophers of that time couldn't agree on the distinction between logical and empirical truth, I think I can safely conclude that this distinction was not at all an established part of the Western culture at that point of time.Rationalists vs. Empiricists is what we call these groups of philosophers now, it is not that they grouped themselves in two schools of 'logical truth' vs. 'empirical truth'. In fact, Hume most probably believed that his own philosophical insights can be derived just by thinking, so they must be logically true. And still, this is quite different from what we today call logically true (i.e., formally provable).
 First off, Hume rejected Descartes' cogito argument. Second of all, in Sceptical Doubts concerning the Operations of the Understanding[1], Hume makes a very rudimentary distinction between "Matters of Fact" (what we'd now call logical truths) and "Relations of Ideas" (what we'd now call empirical truths). Again, these classifications were intuited long before Hume/Descartes, but they exemplify them pretty well.
 You claim that "the now well-established distinction between a and b was intuited long ago", but in the discussion refer to various a'/b' distinctions that separate the whole into quite different parts than today's a/b distinction.I concede that expecting predecessors to split the whole exactly along today's a/b border would be asking too much. On the other hand, there is no objective measure that would allow us to test if a'/b' is similar enough to a/b to support your claim. So if you think it is similar enough, and I think it isn't, it seems to be more a matter of opinion than a matter of knowledge.And my argument on "cogito ergo sum" was not about if Hume would consider it as true or false, but if he would consider it as logical or empirical statement. So your remark about that is true but irrelevant here.
 It's a funny one, because as has already been pointed out, science means more than one thing in English. There's "rigorous study" and there's "natural science". It's assumed that the latter is rigorous and our best philosophical model for this is Popper's falsifiability. And whereas pretty much everyone except string theorists now accepts this model, it's pretty recent. Many ancient Greeks, for instance, favoured thinking hard about a problem over experimental evidence, either before or after the fact.
 This is correct. In another language we'd refer to the distinction with a different word
 In 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.
 For 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 citesYou can click the [v1] link to get a PDF link to the now-retracted information. I really like arXiv's versioned publishing.
 Is the comment that "the proof is wrong" from the author himself?
 Yes, 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.
 In 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 !
 I 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.
 Perhaps 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.
 I suppose, though it would be very strange and disingenuous to leave off the most important implication.
 Well, Turing called his famous paper "On computable numbers, with an application to the Entscheidungsproblem" without really state that the "application" is that he solved it.
 What a fantastic person to point out such a subtlety once it has come to light. Easily steer your fellow scientists right!
 Here's an utterly trivial question. Do most people working on computational problems like this consider themselves mathematicians or scientists?
 I don't speak for computer scientists but I have advanced training in statistics and I think of Computer Science / Statistics as mathematical sciences: they're born of mathematics and have become distinct because of practical considerations.
 Both terms are fluid. Most theoretical computer science research is essentially mathematics, at a high enough level. Some wouldn't necessarily call themselves mathematicians unless their graduate training was in a math department; some might. Some would call themselves scientists insofar as they consider mathematicians a subset of scientists. Most would not consider themselves scientists in the sense of natural sciences like biology.But, most probably don't have a strong opinion on whether/which labels apply! They would say they just do research in TCS.
 Mathematicians, despite the fact that the field is called "Computer Science"
 Dijkstra say Computational Scientist
 Dijkstra is alleged to have said:"Computer science is no more about computers than astronomy is about telescopes."but that's disputed.
 He 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.
 Computational Limitologists (not an actual field, just being tongue-in-cheek here)
 The homepage Blum is referring to is presumably http://theory.cs.uni-bonn.de/blum/blum.var but I can't find an explanation of the flaw there yet.
 The flaw is shown here:
 Welp looks like I have a whole new set of things to learn before I can read a thing :P
 This sounds like a foreign language to me.
 In his comment from yesterday, he wrote that he needed some time. I guess it will be up somewhere next month.
 Thank you for the title update.I know there was a pool on how long till it was disproved. Who had 19days?
 It was known long before 19 days, actually within a week of publication:
 Thank you! That's what I get for falling behind on the theoretical computer science stack exchange.
 Does anyone know who wrote that answer?
 Check 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.
 He 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.
 That'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.
 Awesome, this is science and math working as it should be, kudos to Blum!

Search: