tag:blogger.com,1999:blog-3722233.post5752385947042270044..comments2024-07-08T08:20:09.315-05:00Comments on Computational Complexity: Theorems that you simply don't believeLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger45125tag:blogger.com,1999:blog-3722233.post-78662030583754110782010-07-12T20:53:28.869-05:002010-07-12T20:53:28.869-05:00Here's a paradox which tends to surprise peopl...Here's a paradox which tends to surprise people. It sounds deep and mysterious, but it's really just a simple countability argument: you can't prove, for every real number, that that number equals itself. (Cuz there are more real numbers than there are proofs) See: <a href="http://www.xamuel.com/provability-paradox/" rel="nofollow">A Provability Paradox</a>Xamuelhttp://www.xamuel.comnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-28652907258432358702010-04-13T03:46:16.514-05:002010-04-13T03:46:16.514-05:00Goodstein's theorem isn't that surprising ...Goodstein's theorem isn't that surprising if you ignore the technical nonsense about infinite ordinals. It's just structural induction on trees, a non-arithmetic concept, but completely intuitive as finite combinatorics. Only if you want to shoehorn it into the framework of arithmetic do you have to mess with ordinals. Specifically you represent trees as ordinals up to epsilon-0, which happens to be the upper limit of Peano arithmetic. But it's easier to just reason about the trees directly even though the induction principle on them is in some sense "second order".Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-82269907527109294352010-03-18T14:36:10.326-05:002010-03-18T14:36:10.326-05:00I was really surprised recently to learn that Erdő...I was really surprised recently to learn that Erdős didn't believe the Monty Hall Problem. It doesn't take too much I don't think, to look at Monty Hall and the Birthday paradox from the right angle to make sense of the conclusions.codyhttps://www.blogger.com/profile/11407919985914326282noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-47448385657385236722010-03-15T11:57:08.455-05:002010-03-15T11:57:08.455-05:00I don't understand the point about rationals b...I don't understand the point about rationals being countable. If your problem is that the word size is not the right word to use it has no relation to believability of a theorem.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-71519144938850601452010-03-15T08:41:44.551-05:002010-03-15T08:41:44.551-05:00This point (size x cardinality) illuminates a curi...This point (size x cardinality) illuminates a curious issue about the disbeliefs in theorems: maybe it is the case that mathematics is as hermeneutic as philosophy...Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-4890603445974115902010-03-15T08:39:48.305-05:002010-03-15T08:39:48.305-05:00I think this point (size x cardinality) illustrate...I think this point (size x cardinality) illustrates a point about the disbelief in theorems: maybe it is the case that mathematics is as hermeneutic as philosophy...Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-57637888830547567742010-03-15T08:36:09.693-05:002010-03-15T08:36:09.693-05:00Natural and rational numbers, and SIZE x CARDINALI...Natural and rational numbers, and SIZE x CARDINALITY:<br /><br />I think the point here is that CARDINALITY is taken as a technical term, where only the pure collection of elements is important, while SIZE is taken in the intuitive sense we often apply to structures.<br /><br />Thus, preserving the usual order structures of natural and rational numbers, it is intuitively clear that the SIZE of the structure of rational numbers is GREATER than the SIZE of the structure of the natural numbers (because the latter STRUCTURE can be embedded in the former, and still there are lots of spaces left free...).Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-36329916767373364092010-03-14T23:46:47.944-05:002010-03-14T23:46:47.944-05:00Sorry for resubmitting, Blogger ate my less than s...Sorry for resubmitting, Blogger ate my less than signs in the previous one, I replaced the code of G with 'G'.<br />Let 'G' denotes the code of (Turing-)computable function G.<br />For every computable function F(x,y), there is a computable function G(x) s.t. G(x)=F(x,'G'). Moreover code of G is computable from code of F.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-2205416468116972062010-03-14T23:41:17.910-05:002010-03-14T23:41:17.910-05:00Hi Bhup,
I think Lance meant the recursion theor...Hi Bhup, <br /><br />I think Lance meant the recursion theorem in classical recursion theory (computability theory), not the definability of a function by recursion, i.e.:<br /><br />Let denotes the code of (Turing-)computable function G.<br />For every computable function F(x,y), there is a computable function G(x) s.t. G(x)=F(x,). Moreover code of G is computable from code of F. <br /><br />IMO, recursion theorem is completely believable, as it gives you exactly how to construct the fix point. The only problem is that the proof is seldom made clear enough for the reader.<br /><br />ps: are you a category theorist?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-31554878102261088982010-03-14T21:34:45.532-05:002010-03-14T21:34:45.532-05:00The Banach-Tarski theorem is a theorem, not a para...The<strong> Banach-Tarski theorem</strong> is a theorem, not a paradox. Regarding that theorem, I'd say it doesn't mean math is broken, nor that it casts doubt on the axiom of choice. It does, certainly, if you're trying to model that thing we call "real world", but mathematicians stopped being concerned for that a long time ago.Janomahttps://www.blogger.com/profile/08125807104571129259noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-81838935560069823702010-03-14T13:19:48.434-05:002010-03-14T13:19:48.434-05:00The Isolating Lemma of Mulmuley, Vazirani and Vazi...The Isolating Lemma of Mulmuley, Vazirani and Vazirani, which makes min wt set in *any* set system unique, by assigning poyn large random wts to elements, even though the set system may have exponentially many sets. Has found many appls.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-41100594693667595342010-03-13T15:25:36.061-06:002010-03-13T15:25:36.061-06:00Goodstein's theorem definitely falls into this...<i>Goodstein's theorem definitely falls into this category for me.</i><br /><br />Yes, Goodstein's Theorem does meet the criteria of a Theorem that begs for belief. It is a striking case of proving a Theorem in ZF, and <i>postulating</i> that it must hold over the natural numbers! See <a href="http://alixcomsi.com/10_Goodstein.pdf" rel="nofollow">here</a>.Bhupinder Singh Anandhttps://www.blogger.com/profile/13505076032940030790noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-60925232496344575482010-03-13T11:10:46.946-06:002010-03-13T11:10:46.946-06:00I found the discussion following this post very in...I found the discussion following this post very interesting and enlightening. I can't think of which is my favorite theorem that I don't believe, but I'm surprised to see that disbelief of theorems comes as a surprise to some readers. Just knowing there's a proof out there, or even reading it, cannot be enough to really own a theorem.<br /><br />Unless you are of the Russian school persuasion, where any known result is trivial by definition (just go and read the proof) and anything that hasn't been proved yet is hard by definition.<br /><br />As for finite simple groups, I think we can relax "believing the proof" to: there might be a couple of sporadic groups still out there that were missed on the first pass, but there is no major flaw in any of the arguments, and in particular, no *infinite* family was overlooked. (Disclaimer: This is just a suggestion: I do not know if this accurately represents the opinion of anyone who has a right to an opinion about finite simple groups.)<br /><br />BTW, I'm surprised the 4-color theorem hasn't made an appearance in the comments already.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-12166447186837222082010-03-12T15:43:32.552-06:002010-03-12T15:43:32.552-06:00Dave Barrington- THANKS, I will look at that. Are ...Dave Barrington- THANKS, I will look at that. Are you related to the Dave Barrington that did Barrington's theorem in the first place :-)bill gnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-30797308761151065162010-03-12T15:01:20.513-06:002010-03-12T15:01:20.513-06:00Bill -- your intuition that a width-5 BP cannot do...Bill -- your intuition that a width-5 BP cannot do the mod-101 in poly-size probably tells you that it cannot do the mod-101 function <i>at all</i>. You might want to look at the proof that a width-3 permutation BP can do any function at all, including mod-101. The jump from that to the width-5 result is just quantitative...DaveMBhttp://www.cs.umass.edu/~barringnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-57988969141382422642010-03-12T14:00:56.327-06:002010-03-12T14:00:56.327-06:00Andras- THANKS for the clarification.
I will look ...Andras- THANKS for the clarification.<br />I will look at the Central Limit Theorem more carefully and may come to believe it<br />(less likely with Banach-Tarski!)<br /><br />bill g.GASARCHnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-87457230589811341102010-03-12T13:21:06.439-06:002010-03-12T13:21:06.439-06:00The Central Limit Theorem does not say "stuff...The Central Limit Theorem does not say "stuff is all normal"! As you say, that can't be true. The CLT applies to random variables with <i>finite variance</i>. Otherwise <a href="http://en.wikipedia.org/wiki/Stable_distributions" rel="nofollow">stable distributions</a> are a better bet.<br /><br />By requiring finite variance, one is making the assumption that really horrible outliers are not going to dominate the system's overall behaviour. That's quite an assumption.András Salamonhttp://constraints.wordpress.com/noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-57981788956954053732010-03-12T12:41:10.023-06:002010-03-12T12:41:10.023-06:00Goodstein's theorem definitely falls into this...<a href="http://en.wikipedia.org/wiki/Goodstein%27s_theorem" rel="nofollow">Goodstein's theorem</a> definitely falls into this category for me. The statement of the theorem is not counter-intuitive to me, because I don't have any intuition one way or the other about whether Goodstein sequences should converge. But the <em>proof</em>, on the other hand, is something I just cannot wrap my head around.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-28687601298768310632010-03-12T07:55:35.413-06:002010-03-12T07:55:35.413-06:00Probably the first theorem I ever encountered that...Probably the first theorem I ever encountered that I did not believe is the Well-Ordering theorem, esp. as it applies to the Reals. I think that was actually the first consequence of the Axiom of Choice that got folks suspicious about it.John Pintohttp://www.precproginc.comnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-68314651440377530882010-03-12T00:17:36.833-06:002010-03-12T00:17:36.833-06:00Lance Fortnow tells me he has a hard time believin...<i>Lance Fortnow tells me he has a hard time believing the Recursion Theorem.</i><br /><br />With reason!<br /><br />Given a set X, an element k of X and a function f: X -> X, the theorem states that there is a unique function F: N -> X (where N denotes the set of natural numbers including zero) such that:<br /><br />F(0) = k <br />F(n + 1) = f(F(n)) <br /><br />for any natural number n.<br /><br />In set theory, this `unique' function F is the set {{F(0), k}, {F(1), f(k)}, {F(2), f(f(k))}, ...}.<br /><br />Now, it follows from Godel's Theorem VII of his seminal 1931 paper on undecidable arithmetical propositions that, given a recursive function, say f(x), we can always create an arithmetical relation r(x, y)] such that, for any given natural numbers m, n:<br /><br />f(m) = n if, and only if, r(m, n) holds.<br /><br />Now it can be shown that, although there is a Turing Machine such that, given any natural numbers m and n, TM will decide f(m) = n as true or false, there is no TM such that, given any natural numbers m and n, TM will decide r(m, n) as true.<br /><br />(This is reflected by the assertion that the recursive function f(x) is not strongly representable in Peano Arithmetic PA.)<br /><br />In other words, since f(x) = y is recursively decidable, whilst r(m, n) is not, they are instantiationally equivalent, but computationally different, number-theoretic relations.<br /><br />However, by the Recursion Theorem, they both define a `unique' set F in ZF, and are set-theoretically identical to it if we take k as f(0)!<br /><br />This may not matter much to a set-theorist who takes comfort from Bertrand Russell's quip that mathematics is that subject where we never know what we are talking about, nor whether it is true; it should to a computationalist!Bhupinder Singh Anandhttps://www.blogger.com/profile/13505076032940030790noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-78209373889097134662010-03-11T23:38:33.516-06:002010-03-11T23:38:33.516-06:00I simply do not believe that 25 divided by 5 is 14...I simply do not believe that 25 divided by 5 is 14. <br /><a href="http://www.youtube.com/watch?v=88E0TYijc5I" rel="nofollow"> Here </a> is the proof.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-29216140930096684052010-03-11T22:42:57.544-06:002010-03-11T22:42:57.544-06:001) PCP: Actually I DO find the proof to tell me wh...1) PCP: Actually I DO find the proof to tell me why its true so I do believe it.<br /><br />2) Coding up Monty Hall is NOT the way to understand why its true.<br /><br />3) BP of width 5 for the MOD 3 would be EASY--- just keep track of the number of 1's mod 3. Mod a really large number is more puzzling for me.<br />The fact that the program length is long but poly length --- I don't believe it!<br /><br />4) I find the following comment idiotic, though not for the reasons you might think: <br /><br />``he runs a complexity blog yet does not understand Monty Hall Paradox''<br /><br />YES I was quoting other people.<br />I happen to understand the MH paradox. but that's not the point.<br /><br /> The KEY to knowledge is to NOT be shy about what you don't understand and ask for help on it.<br />People who are shy about what they don't understand and who don't seek help on it as a result remain ignorant. <br /><br />ALSO- once someone understands something its hard to imagine not understanding it. This leads to a<br />certain kind of arrogance which the<br />commenter exhibited.<br /><br />bill g.<br /><br />bill g.GASARCHnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-72775738870145741722010-03-11T20:59:10.629-06:002010-03-11T20:59:10.629-06:00What in the world does this have to do with "...What in the world does this have to do with "belief"? Can't people either know or not know and stop pretending that 'beleving' somehow makes things less suspect?<br /><br />Belief is the pretense of knowing.Unknownhttps://www.blogger.com/profile/02955547844743166800noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-5351678061608848092010-03-11T20:16:50.141-06:002010-03-11T20:16:50.141-06:00And Skolem's paradox (set theory has a countab...<i> And Skolem's paradox (set theory has a countable model) is somewhat disturbing and fascinating. </i><br /><br />Less disturbing and more fascinating once you read the 1922 address, ``Some remarks on axiomatized set theory", delivered in Helsinki before the Fifth Congress of Scandinavian Mathematicians, 4-7 August 1922 (reproduced in Heijenoort's 'From Frege to Godel'), in which Skolem improved upon both the argument and statement of Lowenheim's 1915 theorem---subsequently labelled as the (downwards) Lowenheim-Skolem Theorem. He then drew attention to a :<br /><br />``... peculiar and apparently paradoxical state of affairs. By virtue of the axioms we can prove the existence of higher cardinalities, of higher number classes, and so forth. How can it be, then, that the entire domain B can already be enumerated by means of the finite positive integers? The explanation is not difficult to find. In the axiomatization, `set' does not mean an arbitrarily defined collection; the sets are nothing but objects that are connected with one another through certain relations expressed by the axioms. Hence there is no contradiction at all if a set M of the domain B is non-denumerable in the sense of the axiomatization; for this means merely that within B there occurs no one-to-one mapping Phi of M onto Z_0 (Zermelo's number sequence). Nevertheless there exists the possibility of numbering all objects in B, and therefore also the elements of M, by means of the positive integers; of course such an enumeration too is a collection of certain pairs, but this collection is not a `set' (that is, it does not occur in the domain B)."<br /><br /><i> Banach Tarski Paradox A CS grad students who knows some math says that it shows that mathematics is broken. I would prefer to say it casts doubt on the axiom of choice. </i><br /><br />As to the Axion of Choice, in the same address Skolem emphasised that the Axiom is an essentially non-verifiable statement which does not express any definable content; therefore it cannot be expected to communicate any meaningful information unambiguously under interpretation:<br /><br />``So long as we are on purely axiomatic ground there is, of course, nothing special to be remarked concerning the principle of choice (though, as a matter of fact, new sets are not generated univocally by applications of this axiom); but if many mathematicians---indeed, I believe, most of them---do not want to accept the principle of choice, it is because they do not have an axiomatic conception of set theory at all. They think of sets as given by specification of arbitrary collections; but then they also demand that every set be definable. We can, after all, ask: What does it mean for a set to exist if it can perhaps never be defined? It seems clear that this existence can be only a manner of speaking, which can lead only to purely formal propositions---perhaps made up of very beautiful words---about objects called sets. But most mathematicians want mathematics to deal, ultimately, with performable computing operations and not to consist of formal propositions about objects called this or that."<br /><br />Skolem's remarks seem to be directed against viewing the formal consistency of a formal language as adequate for using it as a language of, both, precise expression and effective communication.<br /><br />Skolem appears to caution (an advisory needed even more today) that such an approach encourages viewing mathematics as a meaningless ``game" by delinking the development of a formal language, first, from its roots as a formalisation of abstractions that we intend it to express precisely; and, second, from its goal as a means of communicating such abstractions effectively and unambiguously.Bhupinder Singh Anandhttps://www.blogger.com/profile/13505076032940030790noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-71558454873355126222010-03-11T20:05:28.889-06:002010-03-11T20:05:28.889-06:00Anonymous and bishnu, please READ what Bill wrote....Anonymous and bishnu, please READ what Bill wrote. He is not saying that HE doesn't believe these. He is saying he knows OTHER PEOPLE who don't "believe" them.Anonymousnoreply@blogger.com