Arora, Sanjeev
Computational Complexity : A Modern Approach / Sanjeev Arora, Boaz Barak - First edition - xxiv, 579 pages : illustrated ; 25 cm.
Includes bibliographical references (p. 549-573) and indexes.
Notational conventions -- Basic Complexity Classes -- The computational model-and why it dosen´t matter -- NP and NP completeness -- Diagonalization -- Space complexity -- The polynomial hierarchy and alternations -- Boolean circuits -- Randomized computation -- Interactive proofs -- Crytography -- Quantum computation -- PCP theorem and hardness of approximation : An introduction -- Lower Bounds for Concrete Computational Models -- Communication complexity -- Circuit lower brounds : Complexity theory´s Waterloo -- Proof complexity -- Advanced topics -- Complexity of counting -- Average case complexity : Levin´s theory -- Hardness amplification and error-correcting codes -- Pseudorandom constructions : Expander and extractors -- Why are circuit lower bounds so difficult? -- Appendix : Mathematical background -- Bibliography --
9780521424264
Computational complexity
Complejidad computacional
Criptografía
Lógica matemática (simbólica)
Computadores cuánticos
511.352 / / A769c
Computational Complexity : A Modern Approach / Sanjeev Arora, Boaz Barak - First edition - xxiv, 579 pages : illustrated ; 25 cm.
Includes bibliographical references (p. 549-573) and indexes.
Notational conventions -- Basic Complexity Classes -- The computational model-and why it dosen´t matter -- NP and NP completeness -- Diagonalization -- Space complexity -- The polynomial hierarchy and alternations -- Boolean circuits -- Randomized computation -- Interactive proofs -- Crytography -- Quantum computation -- PCP theorem and hardness of approximation : An introduction -- Lower Bounds for Concrete Computational Models -- Communication complexity -- Circuit lower brounds : Complexity theory´s Waterloo -- Proof complexity -- Advanced topics -- Complexity of counting -- Average case complexity : Levin´s theory -- Hardness amplification and error-correcting codes -- Pseudorandom constructions : Expander and extractors -- Why are circuit lower bounds so difficult? -- Appendix : Mathematical background -- Bibliography --
9780521424264
Computational complexity
Complejidad computacional
Criptografía
Lógica matemática (simbólica)
Computadores cuánticos
511.352 / / A769c