Computational complexity

Título:

Computational complexity: A modern approach

Autor:

Arora, Sanjeev

Colaboradores:

Barak, Boaz

Temas:

COMPLEJIDAD COMPUTACIONAL ; MODELOS COMPUTACIONALES ; 

ISBN:

9780521424264

País:

Estados Unidos

Publicación:

Nueva York, 2009

Puede solicitar más fácilmente el ejemplar con: F.2 ARO

0. Notational conventions
1. The computacional model- and why it doesn’t matter.
2. NP and NP complétense.
3. Diagonalization.
4. Space complexity.
5. The polinomial hierarchy and alternations.
6. Boolean circuits.
7. Randomized computation.
8. Interactive Prof..
9. Cryptography.
10. Quantum computation.
11. PCP theorem and hardness of approximation: An introduction.
12. Decision trees.
13. Comunication complexity.
14. Circuit lower bpunds: Complexity theory’s Waterloo.
15. Proof complexity.
16. Algebraic computation models.
17. Complexity of counting.
18. Average case complexity: Levin’s theory.
19. Hardness amplification and error-correcting codes.
20. Derandomization.
21. Pseudorandom constructions: Expander and extractors.
22. Proof of PCP theorems and the Fourier transform technique.
23. Why are circuit lower bounds so difficult?
Appendix: Mathematical background.