Logo

Introduction to Computational Complexity

Small book cover: Introduction to Computational Complexity

Introduction to Computational Complexity
by


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.

Home page url

Download or read it online for free here:
Download link
(1MB, PDF)

Similar books

Book cover: Introduction to Complexity TheoryIntroduction to Complexity Theory
by
Complexity theory is the study of the intrinsic complexity of computational tasks. The book is aimed at exposing the students to the basic results and research directions in the field. The focus was on concepts, complex technical proofs were avoided.
(10191 views)
Book cover: Foundations of CryptographyFoundations of Cryptography
by - Cambridge University Press
The book gives the mathematical underpinnings for cryptography; this includes one-way functions, pseudorandom generators, and zero-knowledge proofs. Throughout, definitions are complete and detailed; proofs are rigorous and given in full.
(16064 views)
Book cover: Around Kolmogorov Complexity: Basic Notions and ResultsAround Kolmogorov Complexity: Basic Notions and Results
by - arXiv.org
Algorithmic information theory studies description complexity and randomness. This text covers the basic notions of algorithmic information theory: Kolmogorov complexity, Solomonoff universal a priori probability, effective Hausdorff dimension, etc.
(5804 views)
Book cover: P, NP, and NP-Completeness: The Basics of Complexity TheoryP, NP, and NP-Completeness: The Basics of Complexity Theory
by - 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.
(8808 views)