| Description |
1 online resource (xxiv, 606 pages) : illustrations |
| Contents |
Introduction and preliminaries -- P, NP and NP-completeness -- Variations on P and NP -- More resources, more power -- Space complexity -- Randomness and counting -- The bright side of hardness -- Pseudorandom generators -- Probabilistic proof systems -- Relaxing the requirements -- Appendix A: Glossary of complexity classes -- Appendix B: On the quest for lower bounds -- Appendix C: On the foundations of modern cryptography -- Appendix D: Probabilistic preliminaries and advanced topics in randomization -- Appendix E: Explicit constructions -- Appendix F: Some omitted proofs -- Appendix G: Some computational problems |
| Summary |
Complexity theory is a central field of the theoretical foundations of computer science, concerned with the general study of the intrinsic complexity of computational tasks. This book offers a conceptual perspective on complexity theory intended to serve as an introduction for advanced undergraduates and graduates |
| Bibliography |
Includes bibliographical references (pages 589-599) and index |
| Notes |
Print version record |
| Subject |
Computational complexity.
|
|
Turing machines.
|
|
COMPUTERS -- Machine Theory.
|
|
Computational complexity
|
|
Turing machines
|
|
Berechnungskomplexität
|
| Form |
Electronic book
|
| LC no. |
2008006750 |
| ISBN |
9780511649929 |
|
0511649924 |
|
9780521884730 |
|
052188473X |
|
9780511400773 |
|
0511400772 |
|
9780511804106 |
|
0511804105 |
|
1107186366 |
|
9781107186361 |
|
1282390317 |
|
9781282390317 |
|
0511574347 |
|
9780511574344 |
|
9786612390319 |
|
661239031X |
|
0511398824 |
|
9780511398827 |
|
