Below you find information about
Changes will be announced under news.
| F |
ti |
8-10 |
v 13,14 |
|
D35 |
| F |
ti |
8-10 |
v 19 |
|
E53 |
| F |
ti |
8-10 |
v 20 |
|
D33 |
| F |
to |
10-12 |
v 13,16 |
|
E33 |
| F |
to |
10-12 |
v 14 |
|
D34 |
| F |
to |
10-12 |
v 15 |
|
E53 |
| F |
to |
10-12 |
v 17,19 |
|
D33 |
| F |
to |
13-15 |
v 19 |
|
E33 |
| F |
to |
8-10 |
v 20 |
|
D33 |
top>>
Johan Håstad, <johanh@nada.kth.se>,
790 6289, rum 1435, no offical office-hours make agreement by
email to meet.
Email is the preferred way to contact Johan.
top>>
The course is open to anyone but the target audience
is D4, F4 and the MD-line of SU. The course assumes a working
knowledge of efficient algorithms.
top>>
The goals of the course
The goals of the course are
- to give an overview of modern complexity theory
in order for the student to
- understand the notions of complexity classes and complete problems
- be able to prove statements in complexity theory,
- be able to read (simple) research papers in complexity theory.
top>>
Book
It is likely that we will use chapters from a forthcomining
book of Arora
and Barak. In such a case we would make copies of relevant
chapters from the book.
The traditional book on the subject is:
-
C. H. Papadimitriou: Computational complexity,
Addison Wesley, 1994.
and this might also be used. How to proceed will be discussed
at the first lecture.
top>>
A preliminary plan is given as follows
| F1-3 |
Administration. Introduction to complexity theory and complexity classes.
Models of computation and computability. Time and memory.
(Chapter 1-3)
|
| F4-9 |
Complexity classes (P, NP, coNP, L, NL, PSPACE), reductions
and complete problems. (Chapter 7-10).
|
|---|
| F10-12 |
Randomized algorithms (Chapter 11), approximation algorithms and
approximability (Chapter 13).
|
|---|
| F13-15 |
Additional material to be discussed with course participants.
Please make suggestions!
|
|---|
top>>
We will have three sets of homework problems. Written solutions
will be handed in and discussed orally.
Please note the Nada code of honor
that applies to all our courses.
