How does physics limit what we can compute? This is a fundamental question, not just for mathematics and computer science, but also for physics. I'll argue that the infeasibility of certain computational problems could be taken as a physical principle, analogous to the Second Law of Thermodynamics, or the impossibility of superluminal signalling. I'll first explain what is computational complexity, and then introduce quantum computers: what they are, whether they can be built, and what's known about their capabilities and limitations. Finally, I'll touch on speculative models of computation that would go even beyond quantum computers, using (for example) closed timelike curves or nonlinear Schrodinger equations. I'll emphasize that, even if "intractable" computations occur in a physical system, what really matters is whether those computations have observable consequences.