| ABSTRACT
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.
| |