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

**Mathematics and Computation**

by

**Avi Wigderson**-

**Princeton University Press**

The book provides a broad, conceptual overview of computational complexity theory -- the mathematical study of efficient computation. It is useful for undergraduate and graduate students in mathematics, computer science, and related fields.

(

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

(

**6170**views)

**Think Complexity: Complexity Science and Computational Modeling**

by

**Allen B. Downey**-

**Green Tea Press**

This book is about complexity science, data structures and algorithms, intermediate programming in Python, and the philosophy of science. The book focuses on discrete models, which include graphs, cellular automata, and agent-based models.

(

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

(

**11615**views)