# 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!

## Suitability

This is a pure-maths-style course about the **theory**
of computation; there is no practical computer use involved, but there are
**lots of proofs**, some of them hard! Certain parts of the course
(including some of the more technical proofs) are best suited to
learning from written sources and so are given as guided reading from
the notes. The
course also touches upon some elements of philosophy, and places
relatively high (by mathematics standards) demands on your English
reading and writing skills.

(Students **considering taking this course in
third year** should note that, while the course does not have any formal
third year prerequisites, it requires quite a high level of mathematical
maturity and is certainly harder than a typical third year course. In
the past some third years have done very well, but others have found it
too much of a step up. I would not advise taking the course in third
year unless you have a clear first class average in second year and are
confident of your written English skills and ability to handle abstract
material.)

## Course Materials

These will be available on Blackboard.