Skip to content

Dealing with Intractability and Other Fun Topics: _Computers and Intractability: A Guide to the Theory of NP-Completeness_: The Missing Title from My Advanced Algorithms Course

August 23, 2010

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).

More informally, a problem is NP-complete if and only if:

1) It is possible to verify a yes-answer efficiently, and

2) any of the other NP-hard problems can be shown to be equivalent to it (via an efficient (i.e., polynomial-time) conversion of the inputs).

What is neat about the class of NP-complete (a.k.a. “NPC”) problems is that although they may all seem different, they are in fact equivalent in the sense that if any one of them can be shown to be solvable quickly (i.e., in polynomial time), then so can the rest.

What this means for the working programmer is that if the boss gives the programmer an unreasonable problem to be solved quickly using a computer program, but he/she is able to show that the problem is NP-complete, then the programmer can just tell the boss, “Well, I wasn’t able to write a program to solve the problem quickly, but neither were a lot of other researchers who also tried to solve the same kind of problem, so no matter who you ask, you are very likely to get the same answer.”  In this case, the boss is unlikely to fire the programmer.

One useful aspect of this title is that it includes an appendix with a compendium of NP-complete problems.  By reducing any of these problems to the problem to be solved, one can show that the problem is NP-complete, and hence, unlikely to be solved quickly by any algorithm implemented on any computer program anytime soon.

Leave a Comment

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: