COMP3004 - Computational Complexity

This database contains the 2017-18 versions of syllabuses. Syllabuses from the 2016-17 session are available here.

Note: Whilst every effort is made to keep the syllabus and assessment records correct, the precise details must be checked with the lecturer(s).

Code COMP3004
Year 3
Prerequisites 1002, 1004 and 2008
Term 1
Taught By Fabio Zanasi (50%)
Robin Hirsch (50%)
Aims To address the theoretical and practical limitations of computation. To provide a theoretical framework for modelling computation. The concepts of undecidability and intractability are introduced through a number of examples. The course will convey the proof techniques that are used to classify problems and it is intended that students learn how to apply them in order to classify unfamiliar problems for themselves.
Learning Outcomes To be able to: analyse the complexity of a variety of problems and algorithms; reduce one problem to another; prove that a problem is undecidable; find a polynomial time reduction from one problem to another; determine the complexity class of a decidable problem; categorise the complexity of a language.


Models of Computation
Deterministic Turing machines.
Equivalent Turing machines.
Register machines.

Language recognition.
Language acceptance.
Recursive languages.
Recursively enumerable languages.

The Halting Problem.
Problem reduction.
Undecidability of the tiling problem.
Undecidability of first-order logic.
Other unsolvable problems.

Non-deterministic Turing machines.
Polynomial-time reduction.
Elementary properties of polynomial time reduction.
The complexity classes P, NP, NP-complete.
Cook's theorem.
How to prove NP-hardness of various problems.

Probabilistic Algorithms
Examples of probabilistic algorithms.
How to make 'almost sure' your algorithm is correct.
Complexity analysis of probabilistic algorithms.
The complexity classes PP and BPP.

Other Complexity Classes
Space complexity.
Savitch’s theorem.
Exponential time.
Non-elementary problems.

Method of Instruction

Lecture presentations with associated courseworks.


The course has the following assessment components:

  • Written Examination (2.5 hours, 95%);
  • Coursework Section (2 pieces, 5%).

To pass this course, students must:

  • Obtain an overall pass mark of 40% for all components combined;
  • Obtain a minimum mark of 30% in each component worth ? 30% of the module as a whole.


Reading list available via the UCL Library catalogue.