Complexity theory for Computer Scientists Home Page
is the first question sheet. Any problems email me.
Reading material for next two lectures:
Daniel Pierre Bovet and Pierluigi Crescenzi Chapter 8.
We will start to look at space complexity instead of time complexity.
- Tuesday 22 Sept. 10am Room 1406 Notes
- Friday 25 Sept. 10am Room 1406 Notes
- Tuesday 29 Sept. 10am Room 1145 Notes
- Friday 2 Oct. No Lecture
- Tuesday 6 Oct. 10am-12 Room 1245. Notes
- Friday 9th Oct. 10am-12 Room 1245. Notes
- Tuesday 13 Oct. No Lecture.
- Friday 16 Oct. No Lecture.
- Tuesday 20th Oct. Lecture 10am-12 Room 1245. Notes
- Friday 23th Oct. Lecture 10am-12 Room 1245.Notes
- Tuesday 27th Oct. Lecture 10am-12 Room 1406.
- Tuesday 10th Nov. Lecture 10am-12 Room 1406.
Aims of the Course
Complexity theory can seem complex and unwielding. This course will
show that when used simply as a tool for algorithm analysis and
development, complexity theory can be simple and easy to understand.
This course will present the major theorems not as ends in themselves
but as tools for the algorithm designer.
The course text book will be Introduction to the Theory of
Complexity, by Daniel Pierre Bovet and Pierluigi
Crescenzi published by Prentice Hall. While I recommend you buy
the book, I shall attempt to to provide enough material via slides and
handouts so that you can follow the course without have the book.
The course will cover the following aspects:
The course will be about 15 lectures, Two lectures a week,
with course work. A more detailed course plan will materialise
- Introduction: machine models, undecidability, decidability and
- Defining complexity classes: Machines and languages, reducibility
between languages, time and space complexity.
- Introduction Intractability?: The class NP, NP completeness and
language completeness. Proving NP completeness, 6 basic NP complete
- The class P, some P complete problems.
- Space complexity especially PSPACE. Some PSPACE complete
- If time permits, we shall look at random algorithms.
Preliminary Schedule Lectures on Wednesdays and Fridays at
1pm. Start date 23rd September. This is subject to change. If you
have trouble making these days or dates please say and I will attempt
o work something out.
The world of complexity.
If you understand this picture then don't bother turning up.