next up previous contents
Next: Computation Theory Up: Lent Term 2004: Part Previous: Compiler Construction   Contents


Complexity Theory

Lecturer: Dr A. Dawar

No. of lectures: 12

Prerequisite courses: Data Structures and Algorithms, Computation Theory


Aims


The aim of the course is to introduce the theory of computational complexity. The course will explain measures of the complexity of problems and of algorithms, based on time and space used on abstract models. Important complexity classes will be defined, and the notion of completeness established through a thorough study of NP-completeness. Applications to cryptographic protocols will be considered.


Lectures

Objectives


At the end of the course students should

Recommended books


* Papadimitriou, Ch.H. (1994). Computational complexity. Addison-Wesley.
Sipser, M. (1997). Introduction to the theory of computation. PWS.



next up previous contents
Next: Computation Theory Up: Lent Term 2004: Part Previous: Compiler Construction   Contents
Christine Northeast
Thu Sep 4 15:29:01 BST 2003