From SIPB Cluedumps
Computational Intractability As A Law of Physics
|Date: December 3, 2007, at 3:30 PM|
|Presenters: Scott Aaronson|
| Abstract: In this talk, I'll ask whether the hardness of NP-complete problems would be useful to assume as a physical principle, on par with (say) the Second Law of Thermodynamics or the impossibility of faster-than-light communication. As part of discussing that question, I'll tell you the real story about quantum computing (i.e. not what you've read in the popular press): why this field is tremendously exciting, and why quantum computers could break RSA, Diffie-Hellman, and almost every other public-key cryptosystem used today, but also why we don't believe quantum computers would provide unlimited exponential parallelism.
As time permits, I'll also give a critical assessment of hypothetical computing models that try to go beyond quantum computing. These models involve (for example) closed timelike curves, spacetime singularities, nonlinearities in the Schrödinger equation, or particular many-particle entangled states left over from the Big Bang.
|Bio: Scott Aaronson joined MIT this year as an Assistant Professor of EECS. Before that he received a PhD in CS from UC Berkeley, and was a postdoc at the Institute for Advanced Study in Princeton and the University of Waterloo. Within computer science he is best-known for creating the Complexity Zoo (an online encyclopedia of over 400 complexity classes) and for his widely-read blog. His research interests center around computational complexity theory and the limits of quantum computers. He was invited to speak in the SIPB Cluedump Series because of his numerous hacker credentials, including the ability to use a text editor and to program in BASIC.|