tag:blogger.com,1999:blog-3722233.post2616013063752070358..comments2020-05-27T23:17:32.309-04:00Comments on Computational Complexity: Can we make this problem FUN?Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger5125tag:blogger.com,1999:blog-3722233.post-89345648745662846922009-06-12T10:55:33.012-04:002009-06-12T10:55:33.012-04:001 trillion in base 2 has many more digits than 1 t...1 trillion in base 2 has many more digits than 1 trillion in base 10. If you did it in base 1-trillion - each number would be a single symbol.<br /><br />You could tell an approximate square root for about 6 digits in base 10. An approximate log base-10 for even fewer digits.<br /><br />What you are doing is encoding some of the information of the message in an externally agreed upon set of operations. There is a second conduit of information: the communication protocol itself.mathdadhttps://www.blogger.com/profile/12445433981878357601noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-39431897489755832462009-06-10T19:20:27.681-04:002009-06-10T19:20:27.681-04:00One can do n/2 bits (or digits for your ten finger...One can do n/2 bits (or digits for your ten fingered friends). Basically have one player say the XOR of the first digit of player 1 with the last digit of player 2. Repeat for the second and the pentultimate digit. Once you have gone 1/2 way through, one of the other two players now knows if there is an error. If they both haven't found an error, then the 3 numbers add up as desired. So this is a n/2 + 2 communications. Way off of sqrt(n), but at least much better than n itself.Dean Fosterhttps://www.blogger.com/profile/13906505132477512644noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-57298989379142758382009-06-10T18:44:12.466-04:002009-06-10T18:44:12.466-04:00Supposedly, you are looking for a deterministic so...Supposedly, you are looking for a deterministic solution? If an error probability is allowed, one can employ the protocol for 2-party equality testing (twice).Rasmus Paghhttps://www.blogger.com/profile/05722627403861422993noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-29267333241253719982009-06-10T14:43:07.801-04:002009-06-10T14:43:07.801-04:00Fixed- 10^13 is replaced by 2^n
bill g.Fixed- 10^13 is replaced by 2^n<br /><br />bill g.bil gasarchnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-25135741144229510432009-06-10T14:03:51.494-04:002009-06-10T14:03:51.494-04:00some slight error in the statement - you either me...some slight error in the statement - you either mean \sqrt{log n} or "10^13 was replaced by an n-bit number"...ANumbrOn4HeadIsWrth2InUrHandsnoreply@blogger.com