I'll discuss places where computational complexity theory---the study of what can and can't be feasibly computed---has interacted with fundamental physics in interesting and unexpected ways in recent years. I'll first give a crash course about computer science's P versus NP problem, as well as about quantum computers: what they are, whether they can be scalably built, and what's known today about their capabilities and limitations. Then I'll touch on speculative models of computation that would go even beyond quantum computers, using (for example) closed timelike curves or nonlinearities in the Schrodinger equation. Finally, I'll discuss BosonSampling---a proposal for a rudimentary form of linear-optical quantum computing, which nevertheless seems intractable to simulate using a classical computer---as well as the role of computational complexity in the black hole firewall debate.
address: Department of Astronomy, MC-221, 1002 W. Green Street, Urbana, IL 61801 phone: (217) 333-3090 • fax: (217) 244-7638 • email:email@example.com