Skip to content
Register Sign in Wishlist

P, NP, and NP-Completeness
The Basics of Computational Complexity

  • Date Published: August 2010
  • availability: Available
  • format: Hardback
  • isbn: 9780521192484
Average user rating
(1 review)


Add to wishlist

Other available formats:
Paperback, eBook

Looking for an inspection copy?

Please email to enquire about an inspection copy of this book

Product filter button
About the Authors
  • The focus of this book is the P versus NP Question and the theory of NP-completeness. It also provides adequate preliminaries regarding computational problems and computational models. The P versus NP Question asks whether or not finding solutions is harder than checking the correctness of solutions. An alternative formulation asks whether or not discovering proofs is harder than verifying their correctness. It is widely believed that the answer to these equivalent formulations is positive, and this is captured by saying that P is different from NP. Although the P versus NP Question remains unresolved, the theory of NP-completeness offers evidence for the intractability of specific problems in NP by showing that they are universal for the entire class. Amazingly enough, NP-complete problems exist, and furthermore hundreds of natural computational problems arising in many different areas of mathematics and science are NP-complete.

    • Focuses on the P versus NP Question, which is the most fundamental question of computer science
    • Clarifies the importance of the P versus NP Question and the theory of NP-completeness in general terms
    Read more

    Reviews & endorsements

    'The author is a well-known expert in the field of complexity theory and so is well-qualified to bring out this book which will serve as a very good introductory textbook. The focus on search problems and promise problems in this book is to be appreciated since many books neglect these topics.' S. V. Naaraj, SIGACT News

    Customer reviews

    25th Aug 2013 by AReader

    This is one of the best books in P vs NP. Its one of the best in terms of mathematical rigor and in the sense that there are not too many good ones on this subject. The author however has made numerous misstatements and inaccurate comments in the text which are causing significant confusion to the readers. In addition, some arguments used to prove theorems are technically erroneous. Overall, this book might be interesting to people who are familiar with the subject matter. It is not a good book for self-study or for classes.

    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: August 2010
    • format: Hardback
    • isbn: 9780521192484
    • length: 216 pages
    • dimensions: 229 x 147 x 18 mm
    • weight: 0.49kg
    • contains: 18 b/w illus. 94 exercises
    • availability: Available
  • Table of Contents

    1. Computational tasks and models
    2. The P versus NP Question
    3. Polynomial-time reductions
    4. NP-completeness
    5. Three relatively advanced topics
    Epilogue: a brief overview of complexity theory.

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

    • Analysis of Algorithms
  • 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, Probabilistic Proofs and Pseudorandomness, the two-volume work Foundations of Cryptography, and Computational Complexity: A Conceptual Perspective.

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.