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