tag:blogger.com,1999:blog-3722233.post3322755554011595069..comments2021-05-10T11:58:20.291-05:00Comments on Computational Complexity: My response to the Gasarch P vs NP pollLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger4125tag:blogger.com,1999:blog-3722233.post-47379231259575031162011-11-12T17:27:09.953-06:002011-11-12T17:27:09.953-06:00If P=NP then comedic possibilities become near-cer...If P=NP then comedic possibilities become near-certainties...<br /><br />------------------------------------<br />Bulletin of the AMS, April 1, 2020<br /><i>On the unexpected efficacy of SAT solvers</i><br /><br />A new generation of SAT-solvers has revealed unexpected structure associated to Intel's hardware random number generators (including both the <i>80802 Firmware Hub</i> and its successor <i>Bull Mountain</i>): these bitstreams can be emulated by an GNU-standard MT19937 generator ("Mersenne Twister") initialized with seeds found by SAT-solving. Early expectations that this phenomenon might be confined to Intel hardware have been confounded by the surprising discovery — confirmed in recent months by multiple independent laboratories around the world — that data records associated to photon-counting experiments invariably derive from GNU/MT19937 initialized with SAT-guessable seeds. Are we to conclude that the human experience of reality, in its entirety, is a computational simulation? What can we deduce about the algorithms and even the author(s) of the simulation software? And what are the implications (if any) of these experimental findings with respect to PvsNP? This <i>Bulletin of the AMS</i> special issue is devoted to a discussion of these questions, by a panel that includes Lance Fortnow, Bill GASARCH, Dick Lipton, Scott Aaronson, and the Quantum Pontiffs, with moderators David Deutsch, Doron Zeilberger and Richard Stallman.<br />------------------------------------John Sidleshttps://www.blogger.com/profile/16286860374431298556noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-55318138458127702542011-11-12T14:29:45.452-06:002011-11-12T14:29:45.452-06:00--- Bulletin of the AMS, April 1, 2013 ---
Q: Is ...--- Bulletin of the AMS, April 1, 2013 ---<br /><br /><b>Q:</b> <i>Is the PvsNP problem still relevant?</i><br /><br /><b>A:</b> In recent months the mathematics community's appreciation of the PvsNP problem has been substantially augmented by the construction and release under GPL of a class of public key distribution protocols of which only a subset of measure zero can be cracked by that subset of algorithms whose runtimes are provably in P. Formally these key distribution protocols do not separate P from NP; a much-discussed question is whether they separate P from NP sufficiently "for all practical purposes" (FAPP).<br />------------------------------------------John Sidleshttps://www.blogger.com/profile/16286860374431298556noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-46692943844660187692011-11-11T23:38:17.449-06:002011-11-11T23:38:17.449-06:00"We will show L=RL before I do this poll agai..."We will show L=RL before I do this poll again."<br /><br />Hahaha #1<br />Hahaha #2Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-89453554056037433532011-11-11T21:33:30.632-06:002011-11-11T21:33:30.632-06:00Number theoretic problems are much more resıstent ...Number theoretic problems are much more resıstent to prove lowerbounds than other problems. We don't understand them. We CANNOT even prove their universality for small classes! They have too little simple structure for exploitation. So factoring is not a good candidate to attack. Like other lowerbound the best candidates are combinatorial problems.Anonymousnoreply@blogger.com