Complexity

Module aims

In this module you will have the opportunity to:

  • study time and space complexity classes
  • identify the complexity classes associated with computational problems
  • prove that problems are complete for particular complexity classes
  • develop the ability to fit a particular problem into a class of related problems, and so to appreciate the efficiency attainable by algorithms to solve the particular problem
  • study circuit complexity and the class NC of parallelisable problems
  • study randomised computation and the associated complexity classes
  • explore how the P=NP problem is related to cryptography   

Learning outcomes

Upon successful completion of this module you will be able to:

  • determine to which complexity class a computational problem belongs
  • prove that a computational problem is complete for a class such as NP
  • establish and reason about properties of complexity classes
  • demonstrate to what extent an NP-complete problem has efficient approximate solutions
  • determine whether a problem has efficient parallel solutions
  • evaluate the relationships between public key cryptography, one-way functions and the P=NP problem

Module syllabus

  • Turing machines, decidability, machine independence
  • Time complexity: the classes P and NP, NP-completeness, example problems from logic and graphs
  • Space complexity classes
  • The polynomial hierarchy
  • The parallel computation thesis, Boolean circuits, PRAMs, the class NC
  • Probabilistic algorithms
  • Function problems
  • One-way functions and cryptography

Pre-requisites

The contents of CO240 Models of Computation

Teaching methods

The material will be taught through traditional lectures and tutorial sessions. You will be set unassessed exercises designed to reinforce the material as it is taught. Approximately half of these exercises will be discussed in class; the remainder are intended for you to use for self-study. You will be able to participate in further discussion via the Piazza forum.

Assessments

There will be one written coursework that contributes 20% of the mark for the module. There will be a final written exam, which counts for the remaining 80% of the marks. 

Written and verbal feedback will be given on the assessed coursework. 

Reading list

Supplementary

Module leaders

Dr Iain Phillips