tag:blogger.com,1999:blog-3722233.post399335025709343947..comments2024-11-13T15:38:29.005-06:00Comments on Computational Complexity: What is Random?Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger7125tag:blogger.com,1999:blog-3722233.post-76371511079812461942011-10-05T21:38:40.865-05:002011-10-05T21:38:40.865-05:00CSProf: As Matt Leifer pointed out, using QM for r...CSProf: As Matt Leifer pointed out, using QM for randomness generation is perfectly practical! You can buy a device that does it right now.Scott Aaronsonhttp://www.scottaaronson.comnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-61782932606540748202011-10-04T22:54:16.732-05:002011-10-04T22:54:16.732-05:00I attempted an "exploration" of randomne...I attempted an "exploration" of randomness in the post on this site:<br />http://www.tarotforum.net/showthread.php?t=140495Jasonnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1378867030654107682011-10-04T04:45:40.130-05:002011-10-04T04:45:40.130-05:00Assuming standard Quantum Mechanics, we CAN get ra...Assuming standard Quantum Mechanics, we CAN get random bits (for example by a 2-slit experiment, detecting particles on the other side. The probability of each particle taking the upper path is 1/2. Small discrepancies in building the apparatus do not matter because BPP with "almost perfect coins" = BPP.)<br /><br />I am not claiming that building such devices is practical, just that it would totally upset most of Physics if one assumed that true randomness did not exist in nature.CSProfhttps://www.blogger.com/profile/07212822875614144307noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-64888898809150199692011-10-03T14:48:15.959-05:002011-10-03T14:48:15.959-05:00To mathematicians, “random” is associated to proce...To mathematicians, “random” is associated to processes that spin gold into straw (<i>e.g.</i> deterministic seeds into random-looking strings, plaintext into ciphertext, disequilibrium into equilibrium). To engineers, “random” is associated to time-reversed processes that spin straw into gold (<i>e.g.</i> ciphertext into plaintext, quantum errors into quantum coherence, dilute solutions into concentrated solutions). <br /><br />That so many randomized processes have a physically and/or mathematically and/or and informatically natural time-reversed dual is a great <a href="http://www.youtube.com/watch?v=ejEVczA8PLU" rel="nofollow"><i>Hakuna Matata</i></a> of the 21st century STEM enterprise. :)John Sidleshttps://www.blogger.com/profile/16286860374431298556noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-50329571664581709392011-10-03T12:03:17.447-05:002011-10-03T12:03:17.447-05:00> Random bits would be worth their weight in go...> Random bits would be worth their weight in gold but can we get them?<br /><br />Yes. Stick a photon into a beamsplitter.<br />http://www.idquantique.com/true-random-number-generator/products-overview.htmlMatt Leiferhttp://mattleifer.infonoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-36102428900776345242011-10-03T11:04:17.278-05:002011-10-03T11:04:17.278-05:00Linux (as least) maintains an "entropy pool&q...Linux (as least) maintains an "entropy pool", tossing in random bits from the timing of external events deemed to be random, and hands this out via /dev/random, I think. The entropy only grows at somewhat slow rate, so you can do a "entropy denial-of-service" by continually reading as much as you can. This can be combined with pseudo-random generators to avoid the denial-of-service, but then you lose unpredictability.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-72746986235770971052011-10-03T10:31:16.262-05:002011-10-03T10:31:16.262-05:00Information that we are willing to bet on.
Do yo...<i>Information that we are willing to bet on. </i><br /><br />Do you mean "unwilling to bet on"?Davehttps://www.blogger.com/profile/00243750470577898974noreply@blogger.com