Computers and Intractability: A Guide to the Theory of NP-Completeness

Computers and Intractability stands as a foundational computer science text focused on computational complexity theory and NP-complete problems. Published in 1979, this technical work presents a systematic framework for understanding which computational problems can and cannot be solved efficiently. The book begins with core concepts of algorithm analysis and complexity classes before moving into detailed examinations of NP-completeness. The bulk of the text consists of a comprehensive catalog of over 300 NP-complete problems across multiple domains including logic, graph theory, scheduling, and mathematical programming. Authors Garey and Johnson provide rigorous proofs and reductions while maintaining accessibility through clear explanations and practical examples. The reference format allows readers to look up specific problems and their complexity classifications. This text captures a pivotal moment in computer science when researchers began to formally classify the inherent difficulty of computational problems. Its systematic approach to intractability continues to influence how computer scientists think about algorithmic efficiency and computational limits.

Readers describe this as a dense but comprehensive reference on NP-completeness theory. Many note it requires graduate-level math background to follow. Likes: - Clear organization and thorough appendices - Detailed proofs and reduction techniques - Extensive catalog of NP-complete problems - Still relevant despite age "The reduction techniques taught me how to think about computational complexity" - Goodreads reviewer Dislikes: - Not suitable for beginners - Some sections feel dated - Dense mathematical notation - Limited coverage of approximation algorithms "The notation takes significant effort to parse" - Amazon reviewer Ratings: Goodreads: 4.24/5 (226 ratings) Amazon: 4.6/5 (31 ratings) Most readers emphasize this works better as a reference text than a self-study guide. Computer science students and researchers cite it frequently but note it demands focused study to extract value.

Introduction to the Theory of Computation by Michael Sipser Provides core concepts of computability theory, complexity classes, and formal languages with mathematical rigor and precision.

Algorithm Design by Jon Kleinberg, Éva Tardos Presents algorithmic techniques, computational complexity, and NP-completeness through problem-solving frameworks and real-world applications.

Computational Complexity: A Modern Approach by Sanjeev Arora, Boaz Barak Covers complexity theory from classical results to recent developments in quantum computing and probabilistic proof systems.

The Nature of Computation by Cristopher Moore, Stephan Mertens Explores computational complexity, phase transitions in algorithms, and quantum computing through mathematical and physical perspectives.

Mathematics and Computation: A Theory Revolutionizing Technology and Science by Avi Wigderson Connects computational complexity theory to other mathematical disciplines while examining the foundations of efficient computation.

🔸 Published in 1979, this book became so fundamental to computer science that it's often referred to simply as "Garey and Johnson" or "The Bible of NP-Completeness." 🔸 The book contains an extensive appendix listing over 300 NP-complete problems, which became a crucial reference for researchers determining the computational complexity of new problems. 🔸 David Johnson maintained and published updates to the book's problem list for decades after publication, eventually documenting more than 1,500 NP-complete problems. 🔸 The book's distinctive black cover with white lettering has become iconic in computer science circles, with many researchers able to spot it instantly on a colleague's bookshelf. 🔸 Despite being over 40 years old, the book remains the primary reference for NP-completeness theory and continues to be widely used in graduate-level computer science courses worldwide.