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

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

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

- Notes: Introduction - Practicalities - Chapter 1 - Chapter 2 - Chapter 3 - Chapter 4 (and that's the lot!)
- Exercises:
Sheet 1
- Sheet 2
- Sheet 3
(there is
**no**Sheet 4 - exercises for Chapter 4 are on Sheet 3 - but there will be a sheet of revision exercises) - Solutions: Sheet 1 - Sheet 2 - Sheet 3
- Coursework: Test 2 (due in at or before the lecture on Wednesday 29th April)
- Past Exam Paper: 2013-14

## 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....**Tuesday 11:00-12:00**in**Roscoe 3.4****Wednesday 11:00-12:00**in**University Place 5.211**(note the change from the previous location before Easter!)**Friday 09:00-11:00**(with a short break in the middle) in**Alan Turing G.205**

**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 list of which slots will be used in the remaining weeks:

- Week 10: Tuesday only
- Week 11: All slots
- Week 12: All slots

**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....- Official course descriptions for MATH43012 and MATH63012
- Clay Mathematics Institute "P vs NP" page
- The P-versus-NP page at TU Eindhoven
- The Lego Turing Machine