Skip to content
Register Sign in Wishlist

Computational Complexity
A Conceptual Perspective


  • Date Published: May 2008
  • availability: Available
  • format: Hardback
  • isbn: 9780521884730

£ 62.99

Add to cart Add to wishlist

Other available formats:

Looking for an inspection copy?

This title is not currently available on inspection

Product filter button
About the Authors
  • Complexity theory is a central field of the theoretical foundations of computer science. It is concerned with the general study of the intrinsic complexity of computational tasks; that is, it addresses the question of what can be achieved within limited time (and/or with other limited natural computational resources). This book offers a conceptual perspective on complexity theory. It is intended to serve as an introduction for advanced undergraduate and graduate students, either as a textbook or for self-study. The book will also be useful to experts, since it provides expositions of the various sub-areas of complexity theory such as hardness amplification, pseudorandomness and probabilistic proof systems. In each case, the author starts by posing the intuitive questions that are addressed by the sub-area and then discusses the choices made in the actual formulation of these questions, the approaches that lead to the answers, and the ideas that are embedded in these answers.

    • Presents a conceptual perspective, meaning the text evolves around the underlying intuitive questions on the subject
    • The focus is on motivation and ideas
    • Organized around conceptual themes
    Read more

    Customer reviews

    Not yet reviewed

    Be the first to review

    Review was not posted due to profanity


    , create a review

    (If you're not , sign out)

    Please enter the right captcha value
    Please enter a star rating.
    Your review must be a minimum of 12 words.

    How do you rate this item?


    Product details

    • Date Published: May 2008
    • format: Hardback
    • isbn: 9780521884730
    • length: 632 pages
    • dimensions: 257 x 178 x 41 mm
    • weight: 1.25kg
    • availability: Available
  • Table of Contents

    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. Probabilistic proof systems
    10. 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.

  • Instructors have used or reviewed this title for the following courses

    • Advanced Theory of Computation
    • Computability and Complexity
    • Computation Theory
    • Computational Complexity
    • Computational physics
    • Foundation of Computer Science
    • Models of Computing
    • Randomness in Computing
    • Theory of Computation
  • Author

    Oded Goldreich, Weizmann Institute of Science, Israel
    Oded Goldreich is a Professor of Computer Science at the Weizmann Institute of Science and an Incumbent of the Meyer W. Weisgal Professorial Chair. He is an editor for the SIAM Journal on Computing, the Journal of Cryptology, and Computational Complexity and previously authored the books Modern Cryptography, Probabalistic Proofs and Pseudorandomness and the two-volume work Foundations of Cryptography.

Sign In

Please sign in to access your account


Not already registered? Create an account now. ×

Sorry, this resource is locked

Please register or sign in to request access. If you are having problems accessing these resources please email

Register Sign in
Please note that this file is password protected. You will be asked to input your password on the next screen.

» Proceed

You are now leaving the Cambridge University Press website. Your eBook purchase and download will be completed by our partner Please see the permission section of the catalogue page for details of the print & copy limits on our eBooks.

Continue ×

Continue ×

Continue ×

Find content that relates to you

Join us online

This site uses cookies to improve your experience. Read more Close

Are you sure you want to delete your account?

This cannot be undone.


Thank you for your feedback which will help us improve our service.

If you requested a response, we will make sure to get back to you shortly.

Please fill in the required fields in your feedback submission.