Undergraduate Complexity Theory


Some Mealy machines generating a particular transduction monoid.

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.


Klaus Sutner Instructor: Klaus Sutner sutner@cs

Clock Icon
Office hours: Thursday 16:30–18:00

TBD TA: Ziv Scully zscully@cs

Clock Icon
Office hours: Wednesday 15:00–17:00

TBD TA: Jeremy Ong tto@andrew

Clock Icon
Office hours: Thursday 12:30–14:30

TBD TA: Ben Orgera borgera@andrew

Clock Icon
Office hours: Friday 14:00–16:00