• 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.