P, NP, and NP-Completeness: The Basics of Complexity Theory
by Oded Goldreich
Publisher: Cambridge University Press 2010
ISBN/ASIN: 0521122546
ISBN-13: 9780521122542
Number of pages: 190
Description:
The focus of this book is on the P-vs-NP Question, which is the most fundamental question of computer science, and on the theory of NP-completeness, which is its most influential theoretical discovery. The book also provides adequate preliminaries regarding computational problems and computational models.
Download or read it online for free here:
Download link
(1.9MB, PS)
Similar books
Foundations of Cryptographyby Oded Goldreich - 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.
(11066 views)
Introduction to Computational Complexityby Martin Tompa
Lecture notes for a graduate course on computational complexity taught at the University of Washington. Alternating Turing machines are introduced very early, and deterministic and nondeterministic Turing machines treated as special cases.
(5738 views)
Solving NP-Complete Problemsby F. D. Lewis - University of Kentucky
This is an on-line textbook on heuristic algorithms. From the table of contents: Classes of Problems; Integer Programming; Enumeration Techniques; Dynamic Programming; Approximate Solutions; Local Optimization; Natural Models.
(4934 views)
Measure-Preserving Systemsby 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.
(6623 views)