Welcome to **E-Books Directory**

This is a freely downloadable e-book.

# Introduction to Computational Complexity

Read this book online or download it here for free

**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.