Complexity theory for Computer Scientists Home Page

5 Points

Question Sheet

Here is the first question sheet. Any problems email me.

Schedule

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.

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 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:

Introduction: machine models, undecidability, decidability and feasible computation.
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 problems.
The class P, some P complete problems.
Space complexity especially PSPACE. Some PSPACE complete problems.
If time permits, we shall look at random algorithms.

The course will be about 15 lectures, Two lectures a week, with course work. A more detailed course plan will materialise eventually.

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.

Justin Pearson