Physics Department Seminar University of Alaska Fairbanks

J O U R N A L    C L U B

Complexity Theory as a Language for Describing
Problems in Computer Science
Chris Granade
Physics Dept. & Honors Program

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.

Friday, 1 May 2009
Globe Room, Elvey Building
3:45 PM