On page 46-47, Garey&Johnson list out 6 “basic core” NP-Complete problems. I’ll go over all of them quickly, because they will be used in the reductions for many other problems. But they all start with the “first” NP-Complete problem, Satisfiabiity:
The Problem: Satisfiability (SAT)
The Description: (G&J, p. 39) Given a set U of variables, and a set C of Clauses over U, is there a way to set the variables in U such that every clause in C is true?
(Note that this is not general satisfiability, where the input is any boolean formula. This is really “CNF-Satisfiability”, where the formula is in conjunctive normal form. But you can use logical rules to turn any general logical formula into a CNF formula)
The proof: (p. 39-44) G&J provide a proof of Cook’s Theorem, which provides a “first” NP-Complete problem by representing the formula in non-deterministic Turing Machines. It’s a crazy hard proof, we spent a week (at least) of my graduate school Theory of Computation class going over it, and I still have trouble following it. I think it’s way too hard for undergraduates to follow.
Difficulty: 10
The difficulty of proving Cook’s theorem lies in the large number of details, all done in the pursuit of meeting a definition (NP-completeness) that has just been introduced. In my opinion, using CNF-SAT as the first problem is a mistake.
I suggest satisfiability of (Boolean) circuits as a first problem. If one wants, one can actually do most of the work without even discussing NP-completeness at all. Instead, pose the following problem. One is given a single-tape Turing machine M, whose run time is some known polynomial. (Quadratic, say, for something definite.) The task: construct a Boolean circuit that, when its inputs are the bits of a string x, outputs 1 if M accepts x and 0 if M rejects x.
The proof lays out a sample computation in a 2D grid, with the ith configuration as the ith row of the grid. Each cell, after the first row, is a computation from the previous one. And it’s the same computation for each cell — one simply writes down many copies of the basic circuit.
Once that is done, Cook’s Theorem (for circuits) is almost immediate, using the existence-of-a-witness definition of NP. The reduction from a given M simply produces the circuit, with the input x hard-wired and the witness bits as inputs to the circuit.
From there, 3SAT is not hard to do. Make all of the gates have two inputs; then the correctness of the value of each gate involves only three variables. The CNF for that is necessarily 3CNF. (This is sometimes called the Tseitin transformation.) I would not expect a student to find this on their own, but the ideas are simple and easily understood.
I think this is similar to the way the Cormen Algorithms books approaches it. One problem I run across is that we do NP-Completeness in our Analysis of Algorithms class, and Turing Machines in our Theory of Computation class, and while both are required, students can take them in any order. I’m not sure there _is_ a good way to do this kind of explanation unless they have both topics though.