Undergraduate Complexity Theory

This course provides a gentle introduction into complexity theory, the theory of computations that are restricted by various resource bounds (time, space, energy, ...). We start with a brief tour of the computational universe at large and then home in on the low complexity classes that are most relevant in theoretical computer science such as NP and PSPACE. Time permitting, we may take a look some non-traditional models of computation such as cellular automata or infinite time Turing machines.