# 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:**Fourth year MMath and MSc Pure Mathematics**students are the main target audience and are very welcome.**Third year MMath students**may take the course, as may**third year BSc Mathematics students**subject to timetabling and with the permission of the year tutor. It doesn't rely on any specific third-year courses but it does require a high degree of mathematical maturity. I would not recommend taking it in third year unless you have at least a strong 2:1 average in second year.**Mathematics PhD students**are also welcome and can count the course towards their taught course requirements.**Students from other departments**are welcome to attend on an informal non-examined (auditing) basis; if you want to take the course for credit you should speak to me before registering.

**rigorous proof-based course**(not a course in practical computation), and that it contains some philosophical content which requires stronger

**English language skills**than most mathematics courses.

## Course Materials

Materials for the 2020-21 presentation are available on Blackboard.