Computational complexity : a conceptual perspective

By: Oded GoldreichMaterial type: TextTextPublication details: U.K.: Cambridge University Press, [c2008]Description: 606 pISBN: 9780521884730Subject(s): Computer Science | Computational GeometryLOC classification: QA267.7
Contents:
1 - Introduction and Preliminaries 2 - P, NP, and NP-Completeness 3 - Variations on P and NP 4 - More Resources, More Power? 5 - Space Complexity 6 - Randomness and Counting 7 - The Bright Side of Hardness 8 - Pseudorandom Generators 9 - Probabilistic Proof Systems 10 - Relaxing the Requirements
Summary: Complexity theory is a central field of the theoretical foundations of computer science. It is concerned with the general study of the intrinsic complexity of computational tasks; that is, it addresses the question of what can be achieved within limited time (and/or with other limited natural computational resources). This book offers a conceptual perspective on complexity theory. It is intended to serve as an introduction for advanced undergraduate and graduate students, either as a textbook or for self-study. The book will also be useful to experts, since it provides expositions of the various sub-areas of complexity theory such as hardness amplification, pseudorandomness and probabilistic proof systems. In each case, the author starts by posing the intuitive questions that are addressed by the sub-area and then discusses the choices made in the actual formulation of these questions, the approaches that lead to the answers, and the ideas that are embedded in these answers. --- summary provided by publisher
Tags from this library: No tags from this library for this title. Log in to add tags.
    Average rating: 0.0 (0 votes)
Item type Current library Collection Shelving location Call number Status Notes Date due Barcode Item holds
Book Book ICTS
Mathematic Rack No 5 QA267.7 (Browse shelf (Opens below)) Available Billno:IN 002 693; Billdate: 2017-01-17 00663
Total holds: 0

1 - Introduction and Preliminaries
2 - P, NP, and NP-Completeness
3 - Variations on P and NP
4 - More Resources, More Power?
5 - Space Complexity
6 - Randomness and Counting
7 - The Bright Side of Hardness
8 - Pseudorandom Generators
9 - Probabilistic Proof Systems
10 - Relaxing the Requirements

Complexity theory is a central field of the theoretical foundations of computer science. It is concerned with the general study of the intrinsic complexity of computational tasks; that is, it addresses the question of what can be achieved within limited time (and/or with other limited natural computational resources). This book offers a conceptual perspective on complexity theory. It is intended to serve as an introduction for advanced undergraduate and graduate students, either as a textbook or for self-study. The book will also be useful to experts, since it provides expositions of the various sub-areas of complexity theory such as hardness amplification, pseudorandomness and probabilistic proof systems. In each case, the author starts by posing the intuitive questions that are addressed by the sub-area and then discusses the choices made in the actual formulation of these questions, the approaches that lead to the answers, and the ideas that are embedded in these answers. --- summary provided by publisher

There are no comments on this title.

to post a comment.