**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

**Algorithms and Complexity**

by

**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.

(

**12245**views)

**Solving NP-Complete Problems**

by

**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.

(

**4311**views)

**Foundations of Cryptography**

by

**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.

(

**9795**views)

**Around Kolmogorov Complexity: Basic Notions and Results**

by

**Alexander Shen**-

**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.

(

**735**views)