Introduction to Computational Complexity
by Martin Tompa
Number of pages: 85
These are the lecture notes from a graduate course on Computational Complexity taught at the University of Washington. This text adopts some approaches that will appear unconventional. For example, alternating Turing machines are introduced very early, and deterministic and nondeterministic Turing machines treated as special cases. This simplifies many proofs, such as that of Savitch's Theorem, the P-completeness of the circuit value problem, the NP-completeness of the satisfiability problem, and the PSPACE-completeness of the quantified Boolean formula problem.
Home page url
Download or read it online for free here:
by R. G. Downey, D. R. Hirschfeldt - Springer
Computability and complexity theory are two central areas of research in theoretical computer science. This book provides a systematic, technical development of algorithmic randomness and complexity for scientists from diverse fields.
by Neil D. Jones - The MIT Press
The author builds a bridge between computability and complexity theory and other areas of computer science. Jones uses concepts familiar from programming languages to make computability and complexity more accessible to computer scientists.
by Oded Goldreich - Cambridge University Press
The main focus of the current book is on the P-vs-NP Question and the theory of NP-completeness. Additional topics that are covered include the treatment of the general notion of a reduction between computational problems.
by Johan Håstad
This set of notes gives the broad picture of modern complexity theory, defines the basic complexity classes, gives some examples of each complexity class and proves the most standard relations. The author emphasizes the ideas involved in the proofs.