Skip to content
Register Sign in Wishlist

Computational Complexity
A Conceptual Perspective

$87.99 (P)

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

$ 87.99 (P)

Add to cart Add to wishlist

Other available formats:

Looking for an examination copy?

If you are interested in the title for your course we can consider offering an examination copy. To register your interest please contact providing details of the course you are teaching.

Product filter button
About the Authors
  • This book offers a comprehensive perspective to modern topics in complexity theory, which is a central field of the theoretical foundations of computer science. It addresses the looming question of what can be achieved within a limited amount of time with or without other limited natural computational resources. Can be used as an introduction for advanced undergraduate and graduate students as either a textbook or for self-study, or to experts, since it provides expositions of the various sub-areas of complexity theory such as hardness amplification, pseudorandomness and probabilistic proof systems.

    • 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

    Reviews & endorsements

    "This interesting book... is refreshing to read his [Goldreichs'] opinions... The very strong focus on conceptual issues makes the book indispensible as a reference volume for research libraries."
    M. Bona, University of Florida, CHOICE

    "This book provides very well developed material that should interest advanced students either studying or doing new work on computational complexity. It would also be a valuable text for professionals challenged with solving "hard" computing problems of intending to exploit these types of problems when designing of new types computing systems."
    Brian A. Lawler, Software Engineering Notes

    "The book offers a conceptual perspective on several sub-areas of complexity theory and is intended to be used as a textbook for students and educators as well as for experts who seek an overview of of several sub-areas."
    Gerhard Lischke, Mathematical Reviews

    See more reviews

    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: April 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.

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 ×
warning icon

Turn stock notifications on?

You must be signed in to your Cambridge account to turn product stock notifications on or off.

Sign in Create a Cambridge account arrow icon

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.