Fast-track your application

If you're a final year student in our Faculty of Science and Engineering, you are eligible to fast-track your application for this course. Log in using your University details and submit your interest online.

Learn more about fast-tracking your application for this course

MSc Pure Mathematics and Mathematical Logic / Course details

Year of entry: 2022

Coronavirus information for applicants and offer-holders

We understand that prospective students and offer-holders may have concerns about the ongoing coronavirus outbreak. The University is following the advice from Universities UK, Public Health England and the Foreign and Commonwealth Office.

Read our latest coronavirus information

Course unit details:
Computation and Complexity

Unit code MATH63011
Credit rating 15
Unit level FHEQ level 7 – master's degree or fourth year of an integrated master's degree
Teaching period(s) Semester 2
Offered by Department of Mathematics
Available as a free choice unit? No

Overview

Quite a lot of the mathematics you have studied so far involves using algorithms to solve computational problems. For example, you have probably used Euclid's algorithm to solve the problem of finding the greatest common divisor of two integers. In this course, we abstract a level further, and study the properties of problems and algorithms themselves. The kind of questions we ask are "is there an algorithm to solve EVERY problem?" and "what problems can be solved by an EFFICIENT algorithm?".

Compared with most of mathematics, this area is in its infancy, and many important things remain unknown. The course will take you to the point where you understand the statement of one of the most important open questions in mathematics and computer science: the "P vs NP" problem, for which the Clay Mathematics Foundation is offering a $1,000,000 prize. And who knows, perhaps one day you will be the one to solve it!

Pre/co-requisites

Unit title Unit code Requirement type Description
Computation and Complexity MATH63011 Anti-requisite Compulsory

Students are not permitted to take, for credit, MATH43012 in an undergraduate programme and then MATH63012 in a postgraduate programme at the University of Manchester, as the courses are identical.

Aims

The course unit aims

  • to introduce the main model of computation currently being employed in the theory of computation, Turing machines;
  • to introduce the key parameters quantifying computational complexity (deterministic, non-deterministic, time, space) and the relationships between them.

Learning outcomes

On successful completion of the course unit students should

  • be familiar with Turing machines and their capabilities and limitations, and be able to construct and analyse examples to solve simple problems;
  • have a basic overview of classical complexity theory, including the main parameters quantifying computational complexity classes.
  • be able to classify and compare the decidability and complexity of decision problems in simple cases.
  • understand the statement of, and have an appreciation of some of the issues and concepts surrounding, the "P vs NP" problem.

Syllabus

0. INTRODUCTION (1 lecture): outline introduction to computability and complexity; course practicalities.

1. COMPUTABILITY (11 lectures): problems and solutions; alphabets and languages; Turing machines; recursiveness and the Church-Turing Thesis; multitape machines; coding machines and non-recursive languages; universal computation; non-determinism.

2. COMPUTATIONAL COMPLEXITY (8 lectures): time and space; linear speed up and space reduction; complexity classes; lower bounds and crossing arguments; space and time hierarchy theorems; tractability and P vs NP; polynomial time reduction.

3. COMPLETENESS (9 lectures): NP-completeness; SAT and the Cook-Levin Theorem; NP-completeness by reduction; further examples of NP-complete languages; NP-intermediacy and Ladner's Theorem; PSpace-completeness; oracles and the Baker-Gill-Solovay Theorem.

4. SPACE COMPLEXITY (3 lectures): Savitch's Theorem; the Immerman-Szelepcsenyi Theorem.

Assessment methods

Method Weight
Other 20%
Written exam 80%
  • Mid-semester coursework: two take home tests weighting 20%
  • End of course examination: weighting 80%.

Feedback methods

Tutorials will provide an opportunity for students’ work to be discussed and provide feedback on their understanding.

Recommended reading

Printed notes will be supplied and you should not need to refer to any books. But if you would like an alternative viewpoint, the following texts cover most of the course material:

  • Bovet and Crescenzi, Introduction to the Theory of Complexity, 1994,
  • Papadimitriou, Computational Complexity, 1994,
  • Sipser, Introduction to the Theory of Computation (second edition), 2006.

Study hours

Scheduled activity hours
Lectures 22
Tutorials 11
Independent study hours
Independent study 117

Teaching staff

Staff member Role
Mark Kambites Unit coordinator

Additional notes

This course unit detail provides the framework for delivery in 20/21 and may be subject to change due to any additional Covid-19 impact.  

Please see Blackboard / course unit related emails for any further updates.

Return to course details