Computational complexity : A modern approach
| Autor Principal: | |
|---|---|
| Otros autores o Colaboradores: | |
| Formato: | Libro |
| Datos de publicación: |
Nueva York :
Cambridge University Press,
2009
|
| Temas: | |
| Acceso en línea: | Consultar en el Cátalogo |
| Descripción Física: | xxiv, 579 p. |
| ISBN: | 9780521424264 |
Tabla de Contenidos:
- 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.