You are here: Mathematics > People > Mark Kambites
School of Mathematics

MATH43012/63012 Computation and Complexity (2014-15 presentation)


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!


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

Course Materials

Notes and exercises will also be given out in lectures, but are provided here in case you prefer to have an electronic copy. Please let me know if you need them in a different format because of a disability.

Lecture Times

This is a little complicated, because of a training course I am taking myself during the semester. We have 4 hours timetabled each week, to be used flexibly for lectures and tutorials.... ....but some hours will not be used in some weeks. Every Monday I'll send an email indicating which slots will be used that week for lectures and tutorials. In case it helps to know further in advance, here's a provisional list of which slots will be used: My office hour in Semester 2 of 2014-15 is generally 12:00ish-13:00 on Tuesdays in room 2.144 in the Alan Turing Building. (The "ish" is because I have a lecture immediately beforehand, and will start my office hour at the lecture room: in other words, I'll deal with brief queries from students on the course before going to my office.) Any exceptions will be announced here. If you are unable to come to my office hour then please feel free to email me for an appointment (or just ask a question by email).

Further Links

You may also want to look at....
This page is maintained by Mark Kambites. It was retrieved on 27th January 2015. The text was last manually edited on 20th January 2015 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.