In this course you will learn about the main complexity classes and their relationships (inclusions, equalities, and even a few separations). These are the main topics that we hope to cover:
Time and space complexity, determinism and non-determinism, including: Cook-Levin theorem, PSPACE completeness, Savitch's theorem, Immerman-Szelepcsényi theorem.
Hierarchy theorems.
Oracle computations, relativization as a barrier to complexity separations, the polynomial hierarchy.
Boolean circuits, their relation to Turing machines and to the polynomial hierarchy (Karp-Lipton theorem).
Probabilistic algorithms, their relation to the polynomial hierarchy.
Interactive proofs, IP=PSPACE.
Computer Algebra is the art of using a computer to perform exact mathematical computations. The aim of this course is to cover the fundamental algorithms of this field (from the Fast Fourier Transform to Gröbner bases), while providing the students with a practical familiarity with its uses and applications through tutorials using Maple. After this course, no student will think of using pen-and-paper for long mathematical derivations.