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 Kolmorov Complexity, Quantum Complexity and Real Computation. 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 website.

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