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

**Communication Complexity (for Algorithm Designers)**

by

**Tim Roughgarden**-

**Stanford University**

The two biggest goals of the course are: 1. Learn several canonical problems that have proved the most useful for proving lower bounds; 2. Learn how to reduce lower bounds for fundamental algorithmic problems to communication complexity lower bounds.

(

**1013**views)

**Complexity Theory**

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.

(

**10964**views)

**Complexity and Computation**

by

**Allen Downey**-

**Green Tea Press**

This book is about data structures and algorithms, intermediate programming in Python, complexity science and the philosophy of science. The book covers Graphs, Analysis of algorithms, Scale-free networks, Cellular Automata, Agent-based models, etc.

(

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

(

**8818**views)