Computational Complexity: A Modern ApproachCambridge University Press, 2009 M04 20 This beginning graduate textbook describes both recent achievements and classical results of computational complexity theory. Requiring essentially no background apart from mathematical maturity, the book can be used as a reference for self-study for anyone interested in complexity, including physicists, mathematicians, and other scientists, as well as a textbook for a variety of courses and seminars. More than 300 exercises are included with a selected hint set. The book starts with a broad introduction to the field and progresses to advanced results. Contents include: definition of Turing machines and basic time and space complexity classes, probabilistic algorithms, interactive proofs, cryptography, quantum computation, lower bounds for concrete computational models (decision trees, communication complexity, constant depth, algebraic and monotone circuits, proof complexity), average-case complexity and hardness amplification, derandomization and pseudorandom constructions, and the PCP theorem. |
Contenido
9 | |
Sección 2 | 38 |
Sección 3 | 68 |
Sección 4 | 78 |
Sección 5 | 106 |
Sección 6 | 123 |
Sección 7 | 143 |
Sección 8 | 172 |
Sección 17 | 341 |
Sección 18 | 354 |
Sección 19 | 361 |
Sección 20 | 373 |
Sección 21 | 402 |
Sección 22 | 411 |
Sección 23 | 421 |
Sección 24 | 425 |
Sección 9 | 201 |
Sección 10 | 237 |
Sección 11 | 259 |
Sección 12 | 270 |
Sección 13 | 276 |
Sección 14 | 277 |
Sección 15 | 286 |
Sección 16 | 318 |
Sección 25 | 431 |
Sección 26 | 498 |
Sección 27 | 508 |
Sección 28 | 515 |
Sección 29 | 531 |
Sección 30 | 545 |
549 | |
Otras ediciones - Ver todas
Términos y frases comunes
3SAT algebraic approximation average-case bits Boolean circuits Boolean formula certificate circuit lower bounds clause coins communication complexity constant construction Cook-Levin Theorem decision tree decoding defined Definition denote derandomization deterministic distribution edges efficient encode encryption error-correcting code example Exercise exists extractor fact function f gates graph G hard hash functions hence Hierarchy Theorem implies independent input integer interactive proof language Lemma length linear logspace maps matrix NEXP node nondeterministic notion NP-complete NP-hard one-way functions operation oracle output P/poly pairwise independent PCP Theorem permutation player polynomial polynomial-time algorithm probabilistic algorithms probability at least problem proof of Theorem protocol prove pseudorandom PSPACE quantum computers qubit queries random variable random walk reduction result satisfying assignment Section simulate space steps string subset tape transform Turing machine vector verifier vertex vertices zero