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

**Complexity Theory: A Modern Approach**

by

**Sanjeev Arora, Boaz Barak**-

**Cambridge University Press**

The book provides an introduction to basic complexity classes, lower bounds on resources required to solve tasks on concrete models such as decision trees or circuits, derandomization and pseudorandomness, proof complexity, quantum computing, etc.

(

**15323**views)

**Computational Complexity: A Conceptual Perspective**

by

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

(

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

(

**4166**views)

**Computability and Complexity from a Programming Perspective**

by

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

(

**9705**views)