Prerequisites: NONE.

 

Theoretical Computer Science has shown that computational problems can be classified according to how difficult they are to solve. We now know that some problems are intrinsically impossible to solve in a reasonable amount of time, or with a reasonable amount of resources. This course describes the rigorous model of computation required to compare and classify computational problems and their difficulty, giving an introduction to the theory of computational complexity and the standard complexity classes.