Computer Laboratory > Teaching > Course material 2007–08 > Computer Science Tripos Syllabus and Booklist 2007-2008 > Complexity Theory

next up previous contents
Next: Databases Up: Easter Term 2008: Part Previous: Artificial Intelligence I   Contents


Complexity Theory

Lecturer: Dr A. Dawar

No. of lectures: 12

Prerequisite courses: 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 cryptography will be considered.

Lectures

Objectives

At the end of the course students should

Recommended reading

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



next up previous contents
Next: Databases Up: Easter Term 2008: Part Previous: Artificial Intelligence I   Contents