Computational Complexity: A Conceptual Perspective
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.
What people are saying - Write a review
We haven't found any reviews in the usual places.
2 P NP and NPCompleteness
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
A Glossary of Complexity Classes
B On the Quest for Lower Bounds
C On the Foundations of Modern Cryptography
D Probabilistic Preliminaries and Advanced Topics in Randomization
E Explicit Constructions
F Some Omitted Proofs
G Some Computational Problems
9 Probabilistic Proof Systems
10 Relaxing the Requirements
aforementioned approximation assertion average-case binary Boolean circuits coin tosses Complexity Theory computational problems consider constant construction corresponding cryptography decision problems defined Definition denoted derandomization deterministic distinguisher edges efficient emulation encoding encryption error probability Exercise exists foregoing Furthermore given graph G Guideline holds input instances integer interactive proof system iteration Karp-reduction Lemma length linear log-space log2 logarithmic mapping model of computation no-instances non-deterministic non-uniform Note notion NP-complete NP-proof obtain one-way functions oracle machine output P/poly pairwise independent parties PCP Theorem polynomial polynomial-time reduction probabilistic polynomial-time algorithm probability ensembles procedure promise problem proof of Theorem Proposition protocol prove pseudorandom queries query complexity randomized algorithm Recall reduction refers resp satisfies search problem Section sequence solution solvable solving space complexity Specifically steps strings Turing machine uniform uniformly distributed upper-bounded verifier vertex vertices whereas yes-instances yields zero-knowledge proofs