Personal Homepage of Mark Kambites

MATH43011/63011 Computation and Complexity

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, and some of the issues surrounding, 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!

(Note that this is a proof-based course about the theory of computation, and not a practical computational course.)

Suitability

The course has minimal formal prerequisites, and is taken by quite a range of students:

Course Materials

The 2019-20 presentation of this course has now finished; students who took the course in that year can now access the materials in Blackboard. Materials for the 2020-21 presentation will appear here nearer the time.

Further Links

This page is maintained by Mark Kambites.   It was retrieved on 10th July 2020.   The text was last manually edited on 12th February 2020 but dynamically generated content may have changed more recently.
Opinions expressed are those of the author and do not necessarily reflect policy of the University of Manchester or any other organisation.
Information is correct to the best of the author's knowledge but is provided without warranty.
All content is protected by copyright, and may not be reproduced or further distributed without permission.