tag:blogger.com,1999:blog-3722233.post8501096511560828034..comments2024-03-28T18:17:00.135-05:00Comments on Computational Complexity: Quantum Tecniques/Gen Functions- don't be afraid of new techniquesLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger9125tag:blogger.com,1999:blog-3722233.post-34229455407876718522013-06-29T09:40:08.265-05:002013-06-29T09:40:08.265-05:00The problem with Sam's proof is that it doesn&...The problem with Sam's proof is that it doesn't use the necessary condition involving the greatest common divisor, nor even indicate why it comes up. It can, however, easily be extended to rigorously show that the *average* number of solutions for nearby n is as stated in the theorem.<br /><br />I graded a course last fall where this problem was assigned. The students came up with many inventive proofs, including the "intended" generating function proof. My favorite used the observation that the number of ways of making change for n and for n+a is "of the same order" if a is one of the coin denominations. (The cleanest proof seems to be by induction on the number of denominations so that you can justify claims about orders of growth.) By using Bezout's identity, it follows that the number of ways of making change for n and n+1 is "of the same order". (This solves the main deficiency in Sam's proof.)<br /><br />The proof may be finished in any number of ways, now that we know the number of solutions doesn't depend on any "local" properties of n. For example, we may compute the total number of ways of making change for all m up to n, whether combinatorially or as the volume of a certain simplex in L-dimensional space. Differentiating this function, whether literally or using a combinatorial averaging argument, finishes the proof.<br />Anonymous Rexnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-3214090785460597252013-06-27T06:51:05.752-05:002013-06-27T06:51:05.752-05:00My first thought: I looked at the survey- alas, so...My first thought: I looked at the survey- alas, so many papers to read, so little time.<br /><br />My second thought: You raise the intersting question of<br />`what is the criteria for the best proof', which my post also did. <br />Uses the most elementary techniques?<br />Most insightful?<br />Shortest (not my criteria but others use it)?<br />Does not require cleverness?<br />Is constructive (informally)?<br /><br />While insightful seems like the obvious answer it may not be if the proof is rather long before you get the insight.GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-17123312315716939612013-06-25T20:49:13.165-05:002013-06-25T20:49:13.165-05:00I wonder what you think about Euler's recurren...I wonder what you think about Euler's recurrence for the partition numbers p(n) (= number of ways to write n as the sum of nonincreasing positive integers). There is a purely algebraic generating function proof, there is a very beautiful bijective proof by Franklin of a key lemma, the Pentagonal theorem, which gives the recurrence via a very simple generating function manipulation, and then there is an explicit bijection using partition rank and Dyson maps. I think the mix of Franklin's bijection and the little bit of generating functions is the best proof: the entirely bijective proof maybe gives the best insight but is a bit complicated, while Franklin's bijection gives a very clear idea why the Pentagonal theorem is true. Here is a nice survey of results about integer partitions: http://www.math.ucla.edu/~pak/papers/psurvey.pdfSashohttps://www.blogger.com/profile/09380390882603977159noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-22534284527642664992013-06-25T00:56:25.435-05:002013-06-25T00:56:25.435-05:00I've frequently complained to Bill that most p...<i>I've frequently complained to Bill that most proofs that used Kolmogorov complexity could be rephrased as probabilistic arguments. </i><br /><br />...and most proofs using integral calculus can be rephrased using manual limits of Riemann summations. Down with calculus!<br /><br /><i>I wonder if sometimes people using Kolm. complexity aren't doing it to make their proof look more difficult than it really is.</i><br /><br />My experience with K.C. is the complete opposite. Often a convoluted counting/probabilistic argument that makes the result look impressive devolves into a one liner: "the trace of the computation can be used to reconstruct the input and hence on a Kolmogorov random input the time taken is Omega(n)". No setup, no notation, no definitions. <br /><br />If the techniques above were merely restatements of each other no new problems would have been solved by them. Yet we do know that the exact opposite is the case. The new shorthands introduced by each of the methods listed by Bill above allowed us to solve important open problems. <br />Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-4777525343028031572013-06-24T18:30:50.921-05:002013-06-24T18:30:50.921-05:00I've frequently complained to Bill that most p...I've frequently complained to Bill that most proofs that used Kolmogorov complexity could be rephrased as probabilistic arguments. <br /><br />Does it make a difference? To me it does, because I find probabilistic arguments easier to understand and more intuitive. But that is subjective, I guess. Slightly more objective arguments:<br />(1) I find that the probabilistic argument tends to be shorter than the Kolm. proof. (In particular, proofs using Kolm. complexity sometimes have to set up a lot of notation/definitions first.)<br />(2) I think one can assume the reader has the needed probability background, but not necessarily the Kolm. background. <br />(3) Often, I find that it's not just one technique vs. another, but it ends up being *the same proof*, just that phrasing it in terms of Kolm. complexity obscures (at least to me) what is really going on. I wonder if sometimes people using Kolm. complexity aren't doing it to make their proof look more difficult than it really is.<br /><br />I don't claim the above hold always, but I do claim they hold most of the time Kolm. complexity is used.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-16149109211695877532013-06-24T17:04:33.316-05:002013-06-24T17:04:33.316-05:00Here is maybe a counterexample. For some time, it ...Here is maybe a counterexample. For some time, it has been possible to perform "non-standard" real analysis using genuine infinitesimals. This is certainly more intuitive than standard analysis. But, for the most part, people have been content to work with standard analysis and translate all their infinitesimal intuition into the "standard way." Dealing with the new apparatus is just too cumbersome.Davidhttps://www.blogger.com/profile/13818371550669837787noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-2598663103803668602013-06-24T15:09:18.680-05:002013-06-24T15:09:18.680-05:00Clement: Agreed. I feel "reader" should ...Clement: Agreed. I feel "reader" should be changed to "reviewer" in Jeff's comment :)Arnabnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-77470935701064039292013-06-24T14:00:04.308-05:002013-06-24T14:00:04.308-05:00@Jeff Erickson: even though a proof can be argued ...@Jeff Erickson: even though a proof can be argued to be better when the reader's job is easier, I also have the feeling that "magic" proofs should not be always preferred — including and having them is nice, but for the sake of research, a "mechanical" one is often very useful to the reader as well — it'll give him tools and ideas about how to derive other results.<br />While a ad hoc, very clever and seemingly magic proof is beautiful, very nice, but too often leaves the reader with the impression that not only taking the same approach for another problem is impossible, but even that you need to be a god-like genius to even prove anything.Clement C.https://www.blogger.com/profile/12940652354129428242noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-87734026288907005172013-06-24T10:43:59.686-05:002013-06-24T10:43:59.686-05:00I think this is the usual conflict between relativ...I think this is the usual conflict between relatively mechanical proofs that are easier to derive (generating functions) and "magic" proofs that are easier to understand (combinatorial). The former are better for authors; the latter are better for readers.<br /><br />And readers are more important than authors.JeffEhttps://www.blogger.com/profile/17633745186684887140noreply@blogger.com