Computational Complexity: A Conceptual Perspective (Google eBook)
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.
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