tag:blogger.com,1999:blog-3722233.post4938503300891476119..comments2023-03-29T09:38:56.563-05:00Comments on Computational Complexity: How many ways can you make change of n cents?Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger9125tag:blogger.com,1999:blog-3722233.post-40614976994589679112014-07-27T14:16:34.879-05:002014-07-27T14:16:34.879-05:00This file has appropriate code. I wrote it in grad...This file has appropriate code. I wrote it in grad school, longer ago than I care to think.<br /><br />https://github.com/barak/oaklisp/blob/master/doc/examples/change.oakBarak A. Pearlmutterhttp://www.bcl.hamilton.ienoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-69171973565430109242014-07-14T21:29:56.359-05:002014-07-14T21:29:56.359-05:00THANKS! I fixed both in my copy--- I have much mor...THANKS! I fixed both in my copy--- I have much more to change as well, so the next version will have your corrections and others. GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-49008453814602371892014-07-14T20:39:50.616-05:002014-07-14T20:39:50.616-05:00Also under Def. 2.2, number 4 ought to be d_n = c_...Also under Def. 2.2, number 4 ought to be d_n = c_n + d_n-u<br />(not d_n = b_n + cn_u)Bolutifehttps://www.blogger.com/profile/03393584342744901720noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-92014330667235861632014-07-14T19:04:54.542-05:002014-07-14T19:04:54.542-05:00In your paper http://arxiv.org/pdf/1406.5213v4.pdf...In your paper http://arxiv.org/pdf/1406.5213v4.pdf<br />You seem to have made an error under Def. 1.1 (Case 2) you stated a condition x > 2, but you hadn't previously defined x. Perhaps you meant s?Bolutifehttps://www.blogger.com/profile/03393584342744901720noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-91084663195460827002014-07-08T08:36:18.714-05:002014-07-08T08:36:18.714-05:00Do you know that coin change can be used to discov...Do you know that coin change can be used to discover the anagrams, https://class.coursera.org/progfun-004/forum/thread?thread_id=1440?valjokhttps://www.blogger.com/profile/05913343468893339183noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-4903355449911825412014-06-24T15:23:13.955-05:002014-06-24T15:23:13.955-05:00Perhaps a Computational Complexity repost?Perhaps a <i>Computational Complexity</i> <b><a href="http://blog.computationalcomplexity.org/2013/06/complexity-typecast.html?showComment=1370565789560#c9120162054593065669" rel="nofollow">repost</a></b>?John Sidleshttps://www.blogger.com/profile/16286860374431298556noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-34292861389687936542014-06-23T18:37:31.621-05:002014-06-23T18:37:31.621-05:00Thanks! As soon as I got your comment I got a hold...Thanks! As soon as I got your comment I got a hold of GKP and looked at their proof and wrote it up and posted it as a link off of this blog.GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-55817855612475329342014-06-23T18:35:13.611-05:002014-06-23T18:35:13.611-05:00Hmm. I’ll tell a little story on myself. The count...Hmm. I’ll tell a little story on myself. The count-change program is given in the first edition of Abelson and Sussman, and a problem they give is to come up with a linear time algorithm for the problem. (Here, linear is in n, not log n.) It’s a stunning hard problem in context: early in a programming text — you can do it sort of like the iterative Fibonacci program, you just have to pass 50 or so variables.<br /><br />About 20 years ago, it occurred to me that each of those 50 variable held a linear combination of the values they held at the previous iteration, so you could express evolution of the system as a matrix times a vector, and then use the fast-exponentiation algorithm on the matrix. This made the complexity logarithmic (in infinite precision arithmetic), and enabled me to evaluate the count-change function for huge numbers: 10^40th and thereabouts. And the results were interesting -- the numbers looked like they came out of context-free languages. Lots of regularities in the digits. So I showed this to Laci Babai, and a couple hours later, he came back with the answer via generating functions that consisted of 50 polynomials, one for each congruence class mod 50. [We used the version of the count change problem that included half-dollars.]<br /><br />So the answer was "constant time," again, modulo infinite precision arithmetic. stuhttps://www.blogger.com/profile/05190631846507740664noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-4171761102593161012014-06-23T15:12:20.323-05:002014-06-23T15:12:20.323-05:00Regarding point 1. in the first list: the problem...Regarding point 1. in the first list: the problem (with half-dollars) is worked out in Concrete Mathematics by Graham, Knuth, Pataschnik (page 330 in the 2nd ed.). The book also gives a closed form for this case later in that chapter.Michaelhttps://www.blogger.com/profile/17914961437922395066noreply@blogger.com