Complexity theory for Computer Scientists Home Page

5 Points

Question Sheet

Here 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.

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:

  1. Introduction: machine models, undecidability, decidability and feasible computation.
  2. Defining complexity classes: Machines and languages, reducibility between languages, time and space complexity.
  3. Introduction Intractability?: The class NP, NP completeness and language completeness. Proving NP completeness, 6 basic NP complete problems.
  4. The class P, some P complete problems.
  5. Space complexity especially PSPACE. Some PSPACE complete problems.
  6. 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