tag:blogger.com,1999:blog-3722233.post3619382315475143113..comments2023-10-01T07:37:32.894-05:00Comments on Computational Complexity: Theorems that are less interesting because they are more interestingLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger12125tag:blogger.com,1999:blog-3722233.post-29995442929741067382014-03-05T13:49:26.499-06:002014-03-05T13:49:26.499-06:00Well, general theory plus special considerations w...Well, general theory plus special considerations within a restricted domain can equal interesting result, no? Unknownhttps://www.blogger.com/profile/02166090092426949052noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-24725940952779553972010-10-11T07:59:34.426-05:002010-10-11T07:59:34.426-05:00Bonjour,
Vous trouverez ci-joint mon B...Bonjour,<br /><br /> Vous trouverez ci-joint mon Blog (fermaton.over-blog.com)présentant ma nouvelle théorie mathématique de la conscience.<br /> Par la présente, j'aimerais si vous le voulez bien que les scientifiques de votre communauté me fassent parvenir leur commentaire.<br /><br /> Cordialement<br /><br /> Dr Clovis Simard,phDclovis simardhttps://www.blogger.com/profile/16611166917620977297noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-46400009557910363822010-09-27T07:19:43.241-05:002010-09-27T07:19:43.241-05:00i see.i see.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-40740993685144687632010-09-26T18:08:27.744-05:002010-09-26T18:08:27.744-05:00Perhaps the point is that often (paraphrasing Hamm...Perhaps the point is that often (paraphrasing Hamming) we want insight, not only a proof. In a simpler context the insight may be easier to grasp.Janosnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-51600454023935488432010-09-26T08:17:22.260-05:002010-09-26T08:17:22.260-05:00Here's an example that's not an example. P...Here's an example that's not an example. Probably the Green-Tao theorem can be vastly generalized, to the statement that every set of integers with density at least that of the primes (and indeed considerably smaller) contains arbitrarily long arithmetic progressions. But that wouldn't show that the Green-Tao theorem "has nothing to do with the primes", partly because they make genuine, and very interesting, use of the primes in the proof, and partly because the proof of the general result is likely to be harder rather than easier.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-53048726257766926782010-09-25T06:54:21.146-05:002010-09-25T06:54:21.146-05:00boring posts are boringboring posts are boringAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-23605353644521211392010-09-24T20:02:29.583-05:002010-09-24T20:02:29.583-05:00Suppose someone proves P=NP. How interesting will...Suppose someone proves P=NP. How interesting will results of the form "either P=NP or ..." be? This is about 90% of complexity theory, right?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-29530261072466963292010-09-24T03:56:35.420-05:002010-09-24T03:56:35.420-05:00"Theorems that seem less interesting once you..."Theorems that seem less interesting once you generalize them" have a beauty all their own ... when they are instantiated as <i>Mathematical Magic Tricks</i>.<br /><br />Because if we think about it ... we see that the best mathematical magic tricks are wonderfully amazing when seen as particular instantiations, and yet utterly simple when the general mathematical principle is revealed.<br /><br />As just one example (of many), see Colm Mulcahy's column <a href="http://www.maa.org/columns/colm/cardcolm200506.html" rel="nofollow">A Little Erdös/Szekeres Magic</a>.<br /><br />This occurs in quantum information theory too ... results that seem mysterious and even paradoxical in coarse-grained projective descriptions, become natural and even trivial in fine-grained symplectic descriptions.<br /><br />Indeed, the entire point of math & physics (arguably) is to discover the simple-yet-illuminating general theorems ... without losing sight of the fun and wonder that is associated to the mysterious-seeming special cases.John Sidleshttp://www.mrfm.orgnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-35361311946526881172010-09-23T14:56:27.399-05:002010-09-23T14:56:27.399-05:00> If you know theorems that are less
> inte...> If you know theorems that are less <br />> interesting because they are more <br />> interesting, then please comment.<br /><br />I don't know if that counts, but...<br /><br />Merge sort can be easily modified to sort in n(1+\lg\rho) comparisons where \rho is the number of maximal ascending runs in the input. This is optimal in the worst case over all instances of fixed n and \rho. Insertion sort can be similarly modified (into "local insertion sort", using a (2,4) finger search tree) to sort in n(1+\lg(\inv/n)) comparisons, where $\inv$ is the number of inversions in the input. This is also optimal in the worst case over instances of fixed n and \inv. <br /><br />Step 1: interest.<br />I found all this quite interesting when I learned it, a long time ago, and even more the fact that no known sorting algorithm was known to be optimal in the worst case over all instances of fixed n, \rho and \inv (and that some people had been working on it).<br /><br />Step 2: disappointment <br />I lost a bit of my interest when I realized that, asymptotically, the algorithm simulating both algorithms in parallel is obviously optimal for both \rho and \inv.<br /><br />Step 3: regain of interest<br />I regained interest in the theme when I realized that all those results could be generalized to encodings of permutations, where multiplicative constants do count.<br /><br />Generalization goes both ways?Unknownhttps://www.blogger.com/profile/18194440122547742598noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-33597561301767173552010-09-23T12:27:19.835-05:002010-09-23T12:27:19.835-05:00c.e. means computably enumerable, which is the sam...c.e. means computably enumerable, which is the same as r.e. or recursively enumerable.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-50374618260702726322010-09-23T12:19:56.648-05:002010-09-23T12:19:56.648-05:00pardon my ignorance. what means 'c.e.' ?pardon my ignorance. what means 'c.e.' ?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-2849013351267779342010-09-23T11:42:51.607-05:002010-09-23T11:42:51.607-05:00this blog talks about complexity.
this blog talks...this blog talks about complexity.<br /><br />this blog talks about everything.Anonymousnoreply@blogger.com