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

Computers and Intractability: A Guide to the Theory of NP-Completeness stands as a foundational computer science text on computational complexity theory. The book introduces and explores NP-complete problems - computational challenges that are believed to be inherently difficult to solve efficiently. Michael R. Garey provides a systematic framework for understanding computational complexity, starting with basic concepts and building toward advanced theory. The text includes a comprehensive list of NP-complete problems across multiple domains, from graph theory to scheduling to logic. The book balances theoretical rigor with practical applications, demonstrating how complexity theory impacts real-world computing problems. Technical proofs and formal definitions are complemented by examples and explanations of practical significance. This work remains relevant decades after publication by addressing fundamental questions about the limits of computation and efficiency. The text continues to influence how computer scientists approach algorithm design and problem-solving methodology.

Readers consistently note this book's clear explanations and comprehensive catalog of NP-complete problems. Students and researchers use it as both a reference manual and learning tool. Liked: - Systematic organization and thoroughness of proofs - Detailed appendices and problem classifications - Clear writing style for complex concepts - Problem-reduction diagrams and visual aids - Practical applications and examples Disliked: - Dense mathematical notation can overwhelm beginners - Some sections require advanced theoretical background - Age of examples (from 1979) makes some feel dated - Limited coverage of approximation algorithms - Price remains high for a 40+ year old text Ratings: Goodreads: 4.26/5 (378 ratings) Amazon: 4.6/5 (89 ratings) Notable review: "This book taught me more about careful mathematical writing than any other text. The proofs are models of clarity." - Reader on Mathematics Stack Exchange

Introduction to the Theory of Computation by Michael Sipser This text presents computational complexity theory and formal languages with mathematical rigor and detailed proofs comparable to Garey's treatment of NP-completeness.

Computational Complexity: A Modern Approach by Sanjeev Arora, Boaz Barak This book expands on complexity theory concepts, covering topics beyond NP-completeness including quantum computing and probabilistic computation.

Algorithm Design by Jon Kleinberg, Éva Tardos The text contains extensive coverage of NP-completeness and reduction techniques while connecting theory to practical algorithmic applications.

The Nature of Computation by Cristopher Moore, Stephan Mertens This work bridges complexity theory with physics and mathematics, exploring computational problems through multiple scientific perspectives.

Mathematics and Computation: A Theory Revolutionizing Technology and Science by Avi Wigderson The book connects computational complexity to other mathematical fields, demonstrating the broader impact of computation theory across sciences.

🔹 The book, published in 1979, remains one of the most cited works in computer science, with over 60,000 citations as of 2023. 🔹 Author Michael Garey worked at Bell Labs during its golden age alongside other computing pioneers, including Ken Thompson and Dennis Ritchie, creators of UNIX. 🔹 The book introduced the concept of "NP-completeness" to a wider audience and became known as "the Bible of NP-completeness," establishing a framework still used today to classify computational problems. 🔹 The appendix contains a list of over 300 NP-complete problems, which became a crucial reference for computer scientists determining whether new problems they encountered were likely to be solvable efficiently. 🔹 Despite being over 40 years old, the book addresses questions that remain unsolved today, including the famous P versus NP problem, which carries a $1 million prize from the Clay Mathematics Institute for its solution.