In this talk, complexity theory is presented as a language for describing problems in computer science. This development proceeds by the construction of computational models such as the deterministic Turing machine, and by the construction of complexity classes such as P and NP. The language of complexity theory is then applied to three key applications: the implications for physical theories which violate the Church-Turing thesis, the impact of computational complexity upon evaluating physical theories, and the objective benefits of quantum computers.