• Title: P, NP, and NP-Completeness: The Basics of Computational Complexity
• Author(s) Oded Goldreich
• Publisher: Cambridge University Press; 1 edition (August 16, 2010)
• Paperback: 214 pages
• eBook: HTML and PDF (375 pages)
• Language: English
• ISBN-10: 0521122546
• ISBN-13: 978-0521122542
• Share This:  

Book Description

This undergraduate introduction to computational complexity offers a wide perspective on two central issues in theoretical computer science. The book starts with the relevant background in computability, including Turing machines, search and decision problems, algorithms, circuits, and complexity classes, and then focuses on the P-versus-NP Question and the theory of NP-completeness.

• Oded Goldreich is a professor of Computer Science at the Faculty of Mathematics and Computer Science of Weizmann Institute of Science, Israel. His research interests lie within the theory of computation and are, specifically, the interplay of randomness and computation, the foundations of cryptography, and computational complexity theory. He won the Knuth Prize in 2017.

• Amazon

• Computational Complexity
• Algorithms and Data Structures
• Computational and Algorithmic Mathematics
• Parallel Computing and Programming

• P, NP, and NP-Completeness: The Basics of Computational Complexity (Oded Goldreich)
• The Mirror Site (1) - PDF
• The Mirror Site (2) - PDF (375 pages)

• Think Complexity: Science and Modeling, 2nd Ed. (Allen Downey)
• Computability and Complexity: From a Programming Perspective
• Complexity Theory: A Modern Approach (Sanjeev Arora, et al)
• Solving NP-Complete Problems (Forbes D. Lewis)