MATH43011 - 2010/2011
- Title: Computation and Complexity
- Unit code: MATH43011
- Credits: 15
- Prerequisites: A general mathematics background. Basic familiarity with propositional logic and/or graph theory may be a slight advantage, since these are used for some of the examples, but this is not essential as all required concepts will be covered. The course does not contain any practical computing.
- Co-requisite units: None
- School responsible: Mathematics
- Members of staff responsible:
The course aims
- to introduce the main model of computation currently being employed in the theory of computation, Turing machines;
- to introduce the key parameters quantifying computational complexity (deterministic, non-deterministic, time, space) and the relationships between them.
Brief Description of the unit
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
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!
On successful completion of the course unit students should
- be familiar with Turing machines and their capabilities and limitations, and be able to construct and analyse examples to solve simple problems;
- have a basic overview of classical complexity theory, including the main parameters quantifying computational complexity classes.
- be able to classify and compare the decidability and complexity of decision problems in simple cases.
- understand the statement of, and have an appreciation of some of the issues and concepts surrounding, the "P vs NP" problem.
Future topics requiring this course unit
0. INTRODUCTION (1 lecture): outline introduction to computability and
complexity; course practicalities.
1. COMPUTABILITY (11 lectures): problems and solutions; alphabets and languages; Turing machines; recursiveness and the Church-Turing Thesis; multitape machines; coding machines and non-recursive languages; universal computation; non-determinism.
2. COMPUTATIONAL COMPLEXITY (8 lectures): time and space; linear speed up and space reduction; complexity classes; lower bounds and crossing arguments; space and time hierarchy theorems; tractability and P vs NP; polynomial time reduction.
3. COMPLETENESS (9 lectures): NP-completeness; SAT and the Cook-Levin Theorem; NP-completeness by reduction; further examples of NP-complete languages; NP-intermediacy and Ladner's Theorem; PSpace-completeness; oracles and the Baker-Gill-Solovay Theorem.
4. SPACE COMPLEXITY (3 lectures): Savitch's Theorem; the Immerman-Szelepcsenyi Theorem.
Printed notes will be supplied and you should not need to refer to any books. But if you would like an alternative viewpoint, the following texts cover most of the course material:
- Bovet and Crescenzi, Introduction to the Theory of Complexity, 1994,
- Papadimitriou, Computational Complexity, 1994,
- Sipser, Introduction to the Theory of Computation (second edition), 2006.
Teaching and learning methods
33 hours of lectures, some of which will be used as examples classes, plus weekly office hours. In addition students should expect to do at least seven hours private study each week for this course unit.
- Mid-semester coursework: two take home tests weighting 20%
- End of course examination: two and a half hours weighting 80%.