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.

Instructor: Klaus Sutner

`sutner@cs`

Office hours: Thursday 16:30–18:00

TA: Ziv Scully

`zscully@cs`

Office hours: Wednesday 15:00–17:00

TA: Jeremy Ong

`tto@andrew`

Office hours: Thursday 12:30–14:30

TA: Ben Orgera

`borgera@andrew`

Office hours: Friday 14:00–16:00