Code

COMP3004

Year

3

Prerequisites

1002, 1004 and 2008

Term

1

Taught By

Mark Herbster (50%)
TBC (50%)

Aims

To address the theoretical and practical limitations of computation. To provide a theoretical framework for modelling computation. The concepts of undecidability and intractability are introduced through a number of examples. The course will convey the proof techniques that are used to classify problems and it is intended that students learn how to apply them in order to classify unfamiliar problems for themselves.

Learning Outcomes

To be able to: analyse the complexity of a variety of problems and algorithms; reduce one problem to another; prove that a problem is undecidable; find a polynomial time reduction from one problem to another; determine the complexity class of a decidable problem; categorise the complexity of a language.

Models of Computation

deterministic Turing machines
equivalent Turing machines
Register machines

Languages

Language recognition
Language acceptance
Recursive languages
Recursively enumerable languages

Undecidability

The Halting Problem
Problem reduction
Undecidability of the tiling problem
Undecidability of first-order logic
Other unsolvable problems

Non-determinism

Non-deterministic Turing machines
polynomial-time reduction
elementary properties of polynomial time reduction
the complexity classes P, NP, NP-complete
Cook's theorem
How to prove NP-hardness of various problems

Probabilistic Algorithms

Examples of probabilistic algorithms
How to make 'almost sure' your algorithm is correct
Complexity analysis of probabilistic algorithms
The complexity classes PP and BPP

Lecture presentations with associated courseworks.

The course has the following assessment components:

• Written Examination (2.5 hours, 95%)
• Coursework Section (2 pieces, 5%)

To pass this course, students must:

• Obtain an overall pass mark of 40% for all sections combined

The examination rubric is:
Answer both questions.

M.R. Garey and D.S. Johnson, Computers and Intractability, A Guide to

the Theory of NP-Completeness, Freeman 1986.

V.J. Rayward-Smith: A first Course in Computability, Blackwell

Scientific Publications, 1986.

H. Lewis and C. Papadimitriou: Elements of the

Theory of Computation, Prentice Hall, 1998.

J Hopcroft and J Ullman: Introduction to automata theory, languages, and computation, Addison-Wesley, 1979.

Michael Sipser: Introduction to the Theory of Computation