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
Specifying Systemsby 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.
(15655 views)
Computability and Complexity from a Programming Perspectiveby Neil D. Jones - The MIT Press
The author builds a bridge between computability and complexity theory and other areas of computer science. Jones uses concepts familiar from programming languages to make computability and complexity more accessible to computer scientists.
(11730 views)
Algorithmic Randomness and Complexityby R. G. Downey, D. R. Hirschfeldt - Springer
Computability and complexity theory are two central areas of research in theoretical computer science. This book provides a systematic, technical development of algorithmic randomness and complexity for scientists from diverse fields.
(10107 views)
Complexity Theoryby 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.
(16380 views)