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
Lecture Notes on Computational Complexityby Luca Trevisan
Notes from a graduate courses on Computational Complexity. The first 15 lectures cover fundamentals, the remaining is advanced material: Hastad's optimal inapproximability results, lower bounds for parity in bounded depth-circuits, and more.
(17697 views)
Algorithms and Complexityby Herbert S. Wilf - AK Peters, Ltd.
An introductory textbook on the design and analysis of algorithms. Recursive algorithms are illustrated by Quicksort, FFT, and fast matrix multiplications. Algorithms in number theory are discussed with some applications to public key encryption.
(24585 views)
P, NP, and NP-Completeness: The Basics of Complexity Theoryby 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.
(12048 views)
Mathematics and Computationby Avi Wigderson - Princeton University Press
The book provides a broad, conceptual overview of computational complexity theory -- the mathematical study of efficient computation. It is useful for undergraduate and graduate students in mathematics, computer science, and related fields.
(6408 views)