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

 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.

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
Language: English
ISBN-10: 0521122546
ISBN-13: 978-0521122542
eBook: http://www.wisdom.weizmann.ac.il/~oded/bc-book.html