Computational complexity : a conceptual perspective
Material type:
TextPublication details: Cambridge : Cambridge University Press, 2008Edition: 1st edDescription: xxiv, 606 p. : ilISBN: - 9780521884730
| Item type | Home library | Call number | Status | Date due | Barcode | |
|---|---|---|---|---|---|---|
Libro
|
Biblioteca de la Facultad de Informática | F.2 GOL (Browse shelf(Opens below)) | Available | DIF-04132 | ||
|
Libro
|
Biblioteca de la Facultad de Informática | F.2 GOL (Browse shelf(Opens below)) | Available | DIF-04292 |
Browsing Biblioteca de la Facultad de Informática shelves Close shelf browser (Hides shelf browser)
Incluye índice y bibliografía.
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.
Click on an image to view it in the image viewer