Computational complexity

Título:

Computational complexity: a conceptual perspective

Autor:

Goldreich, Oded

Colaboradores:

Temas:

COMPLEJIDAD COMPUTACIONAL ; 

Edición:

1st ed.

Localización electrónica:

Descripción física:

xxiv, 606 p.:il.

ISBN:

9780521884730

Idioma:

Inglés, 

País:

Estados Unidos

Publicación:

Cambridge : Cambridge University Press, 2008

Nota general:

Incluye índice y bibliografía.

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

1. Introduction and preliminaries 
2. P, NP and NP-completeness
3. Variations on P and NP 
4. More resources, more power?
5. Space complexity
6. Randomness and counting 
7. The bright side of hardness 
8. Pseudorandom generators 
9. Probabiistic proof systems 
10. Relaxing the requirements
Epilogue 
A. Glossary of complexity classes
B. On the quest for lower bounds
C. On the foundations of modern cryptography 
D. Probabilistic preliminaries and advanced topics in randomization
E. Explicit constructions 
F. Some omitted proofs
G. Some computational problems.