Computational Intractability as a Law of Physics Scott Aaronson, Postdoctoral Scholar, Institute for Quantum Computing and Department of Combinatorics and Optimization, University of Waterloo, Canada

Several of the deepest principles in physics can be seen as limitations on technology: for example, the Second Law of Thermodynamics and the impossibility of superluminal communication. In this talk, I'll ask whether the intractability of NP-complete or other 'hard' 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 Schrödinger 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 functions could be efficiently computed in each of these universes, and also about what functions still could not be efficiently computed.