Computational complexity
| Autor Principal: | |
|---|---|
| Formato: | Libro |
| Lengua: | inglés |
| Datos de publicación: |
Reading :
[S.n.],
1995
|
| Edición: | Repr. with corr. ed. |
| Temas: | |
| Acceso en línea: | Consultar en el Cátalogo |
| Descripción Física: | xv, 523 p. : il. ; 24 cm. |
| ISBN: | 0201530821 |
Tabla de Contenidos:
- Part I. Algorithms. 1. Problems and algorithms
- 2. Turing machines
- 3. Computability
- Part II. Logic. 4. Boolean logic
- 5. First-order logic
- 6. Undecidability in logic
- Part III. P and NP. 7. Relations between complexity classes
- 8. Reductions and completeness
- 9. NP-complete problems
- 10. coNP and fuction problems
- 11. Randomized computation
- 12. Cryptography
- 13. Approximability
- 14. One P vs NP
- Part IV. Inside P. 15. Parallel computation
- 16. Logarithmic space
- Part V. Beyond NP. 18. Computation that counts
- 19. Polynomial space
- 20. A glimpse beyond.