**Computational Complexity: A Conceptual Perspective**

by Oded Goldreich

**Publisher**: Cambridge University Press 2008**ISBN/ASIN**: 052188473X**ISBN-13**: 9780521884730**Number of pages**: 632

**Description**:

This book offers a comprehensive perspective to modern topics in complexity theory, which is a central field of the theoretical foundations of computer science. It addresses the looming question of what can be achieved within a limited amount of time with or without other limited natural computational resources. The book can be used as an introduction for advanced undergraduate and graduate students as either a textbook or for self-study, or to experts, since it provides expositions of the various sub-areas of complexity theory such as hardness amplification, pseudorandomness and probabilistic proof systems.

Download or read it online for free here:

**Download link**

(1.4MB, PS)

## Similar books

**From Complexity to Creativity**

by

**Ben Goertzel**-

**Plenum Press**

This text applies the concepts of complexity science to provide an explanation of all aspects of human creativity. The book describes the model that integrates ideas from computer science, mathematics, neurobiology, philosophy, and psychology.

(

**14299**views)

**Introduction to Complexity Theory**

by

**Oded Goldreich**

Complexity theory is the study of the intrinsic complexity of computational tasks. The book is aimed at exposing the students to the basic results and research directions in the field. The focus was on concepts, complex technical proofs were avoided.

(

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

(

**10585**views)

**Parallel Complexity Theory**

by

**Ian Parberry**-

**Prentice Hall**

The rapid growth of parallel complexity theory has led to a proliferation of parallel machine models. This book presents a unified theory of parallel computation based on a network model. It is the first such synthesis in book form.

(

**8311**views)