This is a basic textbook about computational complexity theory, which includes time complexity, space complexity, NP theory, polynomial hierarchy, circuit complexity, stochastic computation and derandomization, counting complexity, interactive proof systems, PCP theorem, and approximate computation and inapproximability.

This book aims for senior undergraduate, graduate, and Ph.D. students, as well as teachers and researchers interested in learning more about computational complexity theory. The book can be used in the following courses: (1) “Introduction to Computational Complexity Theory” for senior undergraduate and graduate students, covering the content of the first three chapters; (2) “Advanced Topics in Computational Complexity Theory” for graduate students, covering the content of the last three chapters; (3) “Algorithm Theory” for senior undergraduate and graduate students, covering relevant content on stochastic computation, derandomization, approximate computation, and inapproximability in Chapters 4 and 6; (4) “Computational Theory” for senior undergraduate and graduate students, centered around Chapter 1, with appropriate supplementation based on credits and the target audience.