You are here: Mathematics > undergraduate > undergraduate studies > course units > level 4 units > MATH43012
School of Mathematics

# MATH43012 - 2008/2009

General Information
• Title: Computational Complexity
• Unit code: MATH43012
• Credits: 15
• Prerequisites: A general mathematics background. Familiarity with the propositional calculus such as MATH20302 Propositional Logic, MATH43001 Predicate Calculus provide would be useful but is not absolutely essential. The course does not contain any practical computing.
• Co-requisite units: None
• School responsible: Mathematics
• Members of staff responsible: Dr. M. Kambites
Page Contents
Other Resources

## Specification

### Aims

The aims of this course are:

• 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, random, time, space) and the relationships between them.

### Brief Description of the unit

It is now rather well known that the Clay Foundation is offering a million dollars for solving the Travelling Salesman Problem, in a nutshell the problem of determining how hard it is to find a salesman's shortest itinerary for visiting some set of towns. It turns out that this is just one of a multitude of similar questions coming from all areas of mathematics. The purpose of this course is to explain how this notion of the 'hardness of a problem' may be captured mathematically and to demonstrate some of the surprisingly rich (and still little understood) structure of mathematical problems themselves that follows from this.

### Learning Outcomes

On successful completion of this course unit students should

• be familiar with the way Turing Machines work and their capabilities and limitations, and be able to construct examples to answer simple problems;
• be aware of the main parameters quantifying the computational complexity classes, and the relations between them, and be able to classify and compare the hardness of problems in simple cases.

None.

### Syllabus

1. Turing Machines: Alphabets, languages, Turing machines, recursive functions, decidability. Multitape and nondeterministic Turing Machines. Universal machines and undecidability. [11 lectures]
2. Time and Space Complexity Classes: The time and space classification, speed up. Space and time hierarchy theorems. P and NP, NP-completeness. P= NP? (Travelling Salesman Problem). Savitch's Theorem and the Immerman-Szelepcsenyi Theorem. [17]
3. Other Complexity Classes : Probabilistic complexity classes, Circuit complexity. [4]

### Textbooks

The course is self contained and you will not be required to consult any books. However the following (all available in the JRUL) cover some of the same material as the course and may provide interesting complementary reading.

• Minsky, Computation, Finite and Infinite Machines, 1967.
• Aho, Hopcroft and Ullman, Design and Analysis of Computer Algorithms, 1974.
• Garey and Johnson, Computers and Intractability, 1979.
• Sipser, Introduction to the Theory of Computation, 1997.
• Minsky and Papert, An Introduction to Computational Geometry, 1969.

### Teaching and learning methods

32 lectures plus weekly office hours.

### Assessment

Mid-semester coursework: two take home tests weighting 20%
End of semester examination: two and a half hours weighting 80%

## Arrangements

### Timing of the course

The classes will take place in the eight weeks prior to the Easter vacation. The examination will take place soon after the Easter vacation and before the normal examination period

On-line course materials for this course unit.