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
Computability and Complexity- Wikibooks
This book is intended as an introductory textbook in Computability Theory and Complexity Theory, with an emphasis on Formal Languages. Its target audience is CS and Math students with some background in programming and data structures.
(8917 views)
Computational Complexity: A Conceptual Perspectiveby Oded Goldreich - Cambridge University Press
This book offers a comprehensive perspective to modern topics in complexity theory. It can be used as an introduction as either a textbook or for self-study, or to experts, since it provides expositions of the various sub-areas of complexity theory.
(11838 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.
(21110 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.
(11727 views)