Share-Ebooks.com

The present set of notes have grown out of a set of courses I have given at
the Royal Institute of Technology. The courses have been given at an in-
troductory graduate level, but also interested undergraduates have followed
the courses.

The main idea of the course has been to give the broad picture of mod-
ern complexity theory. To dene the basic complexity classes, give some
examples of each complexity class and to prove the most standard relations.
The set of notes does not contain the amount of detail wanted from a text-
book. I have taken the liberty of skipping many boring details and tried to
emphasize the ideas involved in the proofs. Probably in many places more
details would be helpful and I would be grateful for hints on where this is
the case.

Most of the notes are at a fairly introductory level but some of the section
contain more advanced material. This is in particular true for the section
on pseudorandom number generators and the proof that IP = PSPACE.
Anyone getting stuck in these parts of the notes should not be disappointed.

To Download this E-Book Click Here.