Welcome to E-Books Directory
This is a freely downloadable e-book.

Introduction to Computational Complexity

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 here:

Download link

 (1MB, PDF)