My Library

University LibraryCatalogue

     
Limit search to items available for borrowing or consultation
 
Look for full text

Search Discovery

Search CARM Centre Catalogue

Search Trove

Add record to RefWorks

E-RESOURCE
Author Goldreich, Oded.

Title Computational complexity : a conceptual perspective / Oded Goldreich.

Published Cambridge ; New York : Cambridge University Press, 2008.

Copies

Location Call No. Status
 UniM INTERNET Resource    AVAILABLE
Physical description 1 online resource (xxiv, 606 pages) : illustrations
Bibliography Includes bibliographical references (pages 589-599) and index.
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.
Subject Computational complexity.
Turing machines.
Electronic book.
ISBN 9780511649929 (electronic bk.)
0511649924 (electronic bk.)
9780521884730 (hardback)
052188473X (hardback)
9780511400773 (ebook)
0511400772 (ebook)
9780511804106 (electronic bk.)
0511804105 (electronic bk.)
1107186366
9781107186361
1282390317
9781282390317
0511574347
9780511574344
9786612390319
661239031X
0511398824
9780511398827

chat loading...