Computational Complexity and Explanations in Physics

Explore the intersection of computational complexity theory and fundamental physics in this lecture by Scott Aaronson from the University of Texas at Austin. Examine how computational intractability might play a direct role in physical explanations themselves, moving beyond its obvious impact on our ability to learn about physics. Investigate three compelling possibilities: whether the exponential difficulty of simulating quantum computers classically supports the many-worlds interpretation of quantum mechanics as proposed by David Deutsch; consider if speculative physical concepts like time travel or quantum nonlinearities should be disfavored because they would grant "absurd computational superpowers"; and analyze whether certain effective descriptions in physics work precisely because violating them is computationally intractable, including examples from black hole thermodynamics and the Second Law of Thermodynamics. Gain insights from Aaronson's expertise in theoretical computer science and quantum computing as he bridges computational complexity with fundamental questions about the nature of physical reality.