Sandbox
From SIPB Cluedumps
[edit] Computational Intractability As A Law of Physics
| Date: December 3, 2007, at 3:30 PM |
| Presenters: Scott Aaronson |
| Location: 56-114 |
| 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. |
