Seminars & Events

Department of Computer Science
"Computational Intractability as a Law of Physics"

DATE: March 7, 2007
TIME: 12:30pm
SPEAKER: Scott Aaronson, University of Waterloo
LOCATION: Ryerson 251, University of Chicago

Description:
Several of the deepest principles in physics can be seen as limits on technology: for example, the Second Law of Thermodynamics and the impossibility of superluminal communication. In this talk, I'll ask whether the hardness of NP-complete computational problems would likewise be useful to assume as a physical principle. To investigate this question, I'll study the computational effects of living in a universe with closed timelike curves, a universe where the Schroedinger equation was nonlinear, a universe with particular many-particle entangled states left over from the Big Bang, or a universe where you could kill yourself with some probability and then 'postselect' on remaining alive. I'll show that one can make definite, nontrivial statements about what problems could be efficiently solved in each of these universes -- and also about what problems still couldn't be.

more info >>

Save the event to your calendar [schedule.ics]