Back in college, the topic that I spent the bulk of my computer science-related studies in preparing for was the design and analysis of algorithms. More specifically, it was actually my introductory course (Computer Science 365a: Design and Analysis of Algorithms) that required the most preparation:  introduction to computer science, discrete mathematics, meta-logic, data structures and programming techniques, set theory, recursive function theory (also known as “computability theory“), and other topics. Included within “discrete mathematics” was elementary set theory, graph theory, propositional calculus, discrete probability theory, some elementary number theory, mathematical games, and other topics as well.

However, compared to the introductory algorithms course, the following algorithms course (Computer Science 465b: Advanced Algorithms) actually required less following preparation, and was in fact much less overall work. There were only four problem sets (one of which, however, was so difficult that I stayed up all night thinking about all three problems and was unable to solve any of them), and most of the reading involved relatively short research monographs.

As a result, the advanced algorithms course stuck out much less in my memory, and until very recently, I was unable to remember the title of one famous book that I had remembered very well at the time, but which I did not use too often, yet still wanted to recommend as a class to those who are interested in studying algorithms.

Recently, however, in reviewing Rice’s Theorem, I was finally able to remember the title: Computers and Intractability: A Guide to the Theory of NP-Completeness, by Michael Garey and David S. Johnson. The book is reportedly the first title ever written on the theory of NP-completeness and computational intractability, and was relatively easy to read for the subject material.

In the opening, the authors give a somewhat humorous story of a person who is in the predicament of having been asked to come up with an algorithm to solve a problem, but who is unable to solve it. What does he do to keep his job? Well, he explains to his boss, “I can’t find an efficient algorithm, but neither can all these famous people.” The book explains that this is the fundamental motivation for proving that a problem is NP-complete (see below for an explanation of this term): that is, that if a problem can be shown to belong to the class of NP-complete problems, then it is equivalent to an entire class of other problems for which no polynomial-time (i.e., efficient) solution has yet been discovered, and hence the problem is unlikely to be solved easily.

Informally, a problem is NP-complete if and only if it satisfies the following two criteria:

1) It belongs to NP (the class of decision problems that can be solved on a non-deterministic Turing machine in polynomial time), and

2) it is NP-hard (that is, it is at least as hard as the hardest problems in NP).