Complexity Theory

Complexity Theory

These set of introductory notes give the broad picture of modern complexity theory, define the basic complexity classes and give some examples of each complexity class.

Publication date: 06 Dec 1999

ISBN-10: n/a

ISBN-13: n/a

Paperback: 130 pages

Views: 19,519

Type: N/A

Publisher: n/a

License: n/a

Post time: 21 Mar 2007 08:28:00

Complexity Theory

Complexity Theory These set of introductory notes give the broad picture of modern complexity theory, define the basic complexity classes and give some examples of each complexity class.
Tag(s): Theory of Computation
Publication date: 06 Dec 1999
ISBN-10: n/a
ISBN-13: n/a
Paperback: 130 pages
Views: 19,519
Document Type: N/A
Publisher: n/a
License: n/a
Post time: 21 Mar 2007 08:28:00
From the Preface:

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 introductory graduate level, but also interested undergraduates have followed the courses.

The main idea of the course has been to give the broad picture of modern complexity theory. To define 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 he 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.
 




About The Author(s)


No information is available for this author.

Johan Håstad

No information is available for this author.


Book Categories
Sponsors