**Introduction to Computational Complexity**

by Martin Tompa

1991**Number of pages**: 85

**Description**:

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.

Download or read it online for free here:

**Download link**

(1MB, PDF)

## Similar books

**P, NP, and NP-Completeness: The Basics of Complexity Theory**

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.

(

**4636**views)

**Measure-Preserving Systems**

by

**Karl Petersen**-

**University of North Carolina**

These notes provide an introduction to the subject of measure-preserving dynamical systems, discussing the dynamical viewpoint; how and from where measure-preserving systems arise; the construction of measures and invariant measures; etc.

(

**6333**views)

**Specifying Systems**

by

**Leslie Lamport**-

**Addison-Wesley Professional**

This book shows how to write unambiguous specifications of complex computer systems. It provides a complete reference manual for the TLA+, the language developed by the author for writing simple and elegant specifications of algorithms and protocols.

(

**8995**views)

**Complexity Theory: A Modern Approach**

by

**Sanjeev Arora, Boaz Barak**-

**Cambridge University Press**

The book provides an introduction to basic complexity classes, lower bounds on resources required to solve tasks on concrete models such as decision trees or circuits, derandomization and pseudorandomness, proof complexity, quantum computing, etc.

(

**11757**views)