Introduction to Complexity Classes
Download this book:
FTP DOWNLOAD SITE
This has been on the web since 1987.
My original (naively ambitious) plan was a coverage of much
larger parts of complexity theory in 2 volumes.
I now see the book as a basic introduction to a field
that has grown in many different directions.
Chapters 1 to 8 has been stable since the early 1990s.
I teach using these notes from time to time.
Chapter 0 was added (circa 2000) when I realized that
Computer Science graduate students today
cannot be assumed to know the basics of computability.
At various times, I teach special topics, and the
result are the additional chapters on
Quantum Complexity and
The last topic, in my view, is the tip of an iceberg that
should engage more complexity theorists.
A link to this book may be found in the
Electronic Colloquium on Computational Complexity
Table of Contents
- Chap. 0: Introduction to Computability
- Chap. 1: Initiation to Complexity Theory
- Chap. 2: The Turing Model: Basic Results
- Chap. 3: Introduction to the Class NP
- Chap. 4: Reducibilities
- Chap. 5: Complete Languages
- Chap. 6: Separation Results
- Chap. 7: Alternating Choices
- Chap. 8: Stochastic Choices
- Chap. 9: Quantum Complexity
- Chap. 10: Theory of Real Computation
- Chap. 11: Kolmogorov Complexity