Skip to content

Computational Complexity A Conceptual Perspective

Best in textbook rentals since 2012!

ISBN-10: 052188473X

ISBN-13: 9780521884730

Edition: 2008

Authors: Oded Goldreich

List price: $93.00
Shipping box This item qualifies for FREE shipping.
Blue ribbon 30 day, 100% satisfaction guarantee!
what's this?
Rush Rewards U
Members Receive:
Carrot Coin icon
XP icon
You have reached 400 XP and carrot coins. That is the daily max!


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. 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.
Customers also bought

Book details

List price: $93.00
Copyright year: 2008
Publisher: Cambridge University Press
Publication date: 4/28/2008
Binding: Hardcover
Pages: 632
Size: 7.01" wide x 10.12" long x 1.61" tall
Weight: 2.750
Language: English

List of Figures
Organization and Chapter Summaries
Introduction and Preliminaries
A Brief Overview of Complexity Theory
Characteristics of Complexity Theory
Contents of This Book
Approach and Style of This Book
Standard Notations and Other Conventions
Computational Tasks and Models
Computational Tasks
Uniform Models (Algorithms)
Non-uniform Models (Circuits and Advice)
Complexity Classes
Chapter Notes
P, NP, and NP-Completeness
The P Versus NP Question
The Search Version: Finding Versus Checking
The Decision Version: Proving Versus Verifying
Equivalence of the Two Formulations
Two Technical Comments Regarding NP
The Traditional Definition of NP
In Support of P Different from NP
Philosophical Meditations
Polynomial-Time Reductions
The General Notion of a Reduction
Reducing Optimization Problems to Search Problems
Self-Reducibility of Search Problems
Digest and General Perspective
The Existence of NP-Complete Problems
Some Natural NP-Complete Problems
NP Sets That Are Neither in P nor NP-Complete
Reflections on Complete Problems
Three Relatively Advanced Topics
Promise Problems
Optimal Search Algorithms for NP
The Class coNP and Its Intersection with NP
Chapter Notes
Variations on P and NP
Non-uniform Polynomial Time (P/poly)
Boolean Circuits
Machines That Take Advice
The Polynomial-Time Hierarchy (PH)
Alternation of Quantifiers
Non-deterministic Oracle Machines
The P/poly Versus NP Question and PH
Chapter Notes
More Resources, More Power?
Non-uniform Complexity Hierarchies
Time Hierarchies and Gaps
Time Hierarchies
Time Gaps and Speedup
Space Hierarchies and Gaps
Chapter Notes
Space Complexity
General Preliminaries and Issues
Important Conventions
On the Minimal Amount of Useful Computation Space
Time Versus Space
Circuit Evaluation
Logarithmic Space
The Class L
Log-Space Reductions
Log-Space Uniformity and Stronger Notions
Undirected Connectivity
Non-deterministic Space Complexity
Two Models
NL and Directed Connectivity
A Retrospective Discussion
PSPACE and Games
Chapter Notes
Randomness and Counting
Probabilistic Polynomial Time
Basic Modeling Issues
Two-Sided Error: The Complexity Class BPP
One-Sided Error: The Complexity Classes RP and coRP
Zero-Sided Error: The Complexity Class ZPP
Randomized Log-Space
Exact Counting
Approximate Counting
Searching for Unique Solutions
Uniform Generation of Solutions
Chapter Notes
The Bright Side of Hardness
One-Way Functions
Generating Hard Instances and One-Way Functions
Amplification of Weak One-Way Functions
Hard-Core Preicates
Reflections on Hardness Amplification
Hard Problems in E
Amplification with Respect to Polynomial-Size Circuits
Amplification with Respect to Exponential-Size Circuits
Chapter Notes
Pseudorandom Generators
The General Paradigm
General-Purpose Pseudorandom Generators
The Basic Definition
The Archetypical Application
Computational Indistinguishability
Amplifying the Stretch Function
Non-uniformly Strong Pseudorandom Generators
Stronger Notions and Conceptual Reflections
Derandomization of Time-Complexity Classes
Defining Canonical Derandomizers
Constructing Canonical Derandomizers
Technical Variations and Conceptual Reflections
Space-Bounded Distinguishers
Definitional Issues
Two Constructions
Special-Purpose Generators
Pairwise Independence Generators
Small-Bias Generators
Random Walks on Expanders
Chapter Notes
Probabilistic Proof Systems
Introduction and Preliminaries
Interactive Proof Systems
Motivation and Perspective
The Power of Interactive Proofs
Variants and Finer Structure: An Overview
On Computationally Bounded Provers: An Overview
Zero-Knowledge Proof Systems
Definitional Issues
The Power of Zero-Knowledge
Proofs of Knowledge - A Parenthetical Subsection
Probabilistically Checkable Proof Systems
The Power of Probabilistically Checkable Proofs
PCP and Approximation
More on PCP Itself: An Overview
Chapter Notes
Relaxing the Requirements
Search or Optimization
Decision or Property Testing
Average-Case Complexity
The Basic Theory
Chapter Notes
Glossary of Complexity Classes
Algorithm-Based Classes
Time Complexity Classes
Space Complexity Classes
Circuit-Based Classes
On the Quest for Lower Bounds
Boolean Circuit Complexity
Basic Results and Questions
Monotone Circuits
Bounded-Depth Circuits
Formula Size
Arithmetic Circuits
Univariate Polynomials
Multivariate Polynomials
Proof Complexity
Logical Proof Systems
Algebraic Proof Systems
Geometric Proof Systems
On the Foundations of Modern Cryptography
Introduction and Preliminaries
The Underlying Principles
The Computational Model
Organization and Beyond
Computational Difficulty
One-Way Functions
Hard-Core Predicates
Computational Indistinguishability
Pseudorandom Generators
Pseudorandom Functions
The Simulation Paradigm
The Actual Definition
A General Result and a Generic Application
Definitional Variations and Related Notions
Encryption Schemes
Beyond Eavesdropping Security
Signatures and Message Authentication
General Cryptographic Protocols
The Definitional Approach and Some Models
Some Known Results
Construction Paradigms and Two Simple Protocols
Concluding Remarks
Probabilistic Preliminaries and Advanced Topics in Randomization
Probabilistic Preliminaries
Notational Conventions
Three Inequalities
The Leftover Hash Lemma
Formal Setting
Known Results
Randomnes Extractors
Definitions and Various Perspectives
Explicit Constructions
Error-Correcting Codes
Basic Notions
A Few Popular Codes
Two Additional Computational Problems
A List-Decoding Bound
Expander Graphs
Definitions and Properties
Some Omitted Proofs
Proving That PH Reduces to #P
Proving That IP(f) [characters not reproducible] AM(O(f)) [characters not reproducible] AM(f)
Emulating General Interactive Proofs by AM-Games
Linear Speedup for AM
Some Computational Problems
Boolean Formulae
Finite Fields, Polynomials, and Vector Spaces
The Determinant and the Permanent
Primes and Composite Numbers