COMP0017 Computability and Complexity Theory

This database contains the 2018-19 versions of syllabuses. These are still being finalised and changes may occur before the start of the session.

Syllabuses from the 2017-18 session are available here.

Academic session

2018-19

Module

Computability and Complexity Theory

Code

COMP0017

Module delivery

1819/A6U/T1/COMP0017 Undergraduate

Related deliveries

None

Prior deliveries

COMP3004

Level

Undergraduate

FHEQ Level

L6

FHEQ credits

15

Term/s

Term 1

Module leader

Hirsch, Robin

Contributors

Hirsch, Robin

Zanasi, Fabio

Module administrator

Ball, Louisa

Levit, Getrud

Aims

The module addresses the theoretical and practical limitations of computation and provides a theoretical framework for modelling computation. The concepts of undecidability and intractability are introduced through a number of examples. The module 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

On successful completion of the module, a student will be able to:

  1. analyse the complexity of a variety of problems and algorithms;
  2. reduce one problem to another;
  3. prove that a problem is undecidable;
  4. find a polynomial time reduction from one problem to another;
  5. determine the complexity class of a decidable problem;
  6. categorise the complexity of a language.

Availability and prerequisites

This module delivery is available for selection on the below-listed programmes. The relevant programme structure will specify whether the module is core, optional, or elective.

In order to be eligible to select this module as optional or elective, where available, students must meet all prerequisite conditions to the satisfaction of the module leader. Places for students taking the module as optional or elective are limited and will be allocated according to the department’s module selection policy.

Programmes on which available:

  • BSc Computer Science (Year 3)
  • MEng Computer Science (Year 3)
  • MEng Mathematical Computation (Year 3)
  • BASc Arts and Sciences (Sciences and Engineering)

Prerequisites:

In order to be eligible to select this module, student must have:

Content

Models of Computation

  • Deterministic Turing machines.
  • Equivalent Turing machines.
  • Register machines.

Languages

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

Undecidability

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

Non-determinism

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

An indicative reading list is available via http://readinglists.ucl.ac.uk/departments/comps_eng.html.

Delivery

The module is delivered through a combination of lectures and problem classes.

Assessment

This module delivery is assessed as below:

#

Title

Weight (%)

Notes

1

Written examination (2hrs 30 mins)

90

 

2

Coursework

10

 

In order to pass this module delivery, students must:

  • achieve an overall weighted module mark of at least 40%; and
  • achieve a mark of at least 30% in any components of assessment weighed ≥ 30% of the module.

Where a component comprises multiple assessments, the minimum mark applies to the overall component.