Course home page
Course Information
Lectures
Mondays and Wednesdays 10-12 T3
First lecture: 9th January
Classroom sessions
Tuesdays 14-16 A211
First session; 17th January
Lecturer
Chris Purcell
Teaching Assistants
Janne Korhonen, Tuomo Lempiäinen
Topics
Models of computation: Turing machines, RAM machines, Boolean
circuits
Modes of computation: deterministic, nondeterministic, parallel,
randomised, alternating
Basic notions of computational complexity: complexity measures and
complexity classes, hierarchy theorems, reductions between problems,
completeness
Central complexity classes: P, NP, PSPACE, NC, polynomial time
hierarchy, etc.
Design of completeness proofs, especially for NP-completeness
Applications and extensions: approximability, counting, games,
cryptographic protocols
Learning Outcomes
Once you have taken the course, you master the key complexity
classes, their underlying models of computation, and
relationships.
You are able to formalise and abstract from a given computational
task relevant computational problems and argue that they belong
to appropriate complexity classes.
You understand the concept of reductions and how it can be used
to order problems by their computational complexity. You are able
to show using reductions that a problem is complete for a central
complexity class (such as NP) and you understand the
importance and implications of such a result.
You are familiar with the concepts of randomised, approximation,
and parallel computation and aware of related complexity classes
and their relation to other complexity classes and their models of
computation.