My class's attention span was running down like sand through an hourglass. Eyes were starting to glaze even in the front row. Breathing had become soft and regular in the middle of the room. Heads were tilted back and eyes shut in the rear.
There were fifteen minutes left to go in my lecture on NP-completeness, and I couldn't really blame them. They had already seen several reductions like the ones presented here, but NP-completeness reductions are easier to create than to understand or explain. They had to watch one being created in order to appreciate this.
I reached for my trusty copy of Garey and Johnson's book [GJ79], which contains a list of over four hundred different known NP-complete problems in an appendix in the back.
``Enough of this!'' I announced loudly enough to startle those in the back row. ``NP-completeness proofs are routine enough that we can construct them on demand. I need a volunteer with a finger. Can anyone help me?''
A few students in the front held up their hands. A few students in the back held up their fingers. I opted for one from the front row.
``Select a problem at random from the back of this book. I can prove the hardness of any of these problems in the now twelve minutes remaining in this class. Stick your finger in and read me a problem.''
I had definitely gotten their attention. But I could have done that by offering to juggle chainsaws. Now I had to deliver results without cutting myself into ribbons.
The student picked out a problem. ``OK, prove that Inequivalence of Programs with Assignments is hard,'' she said.
``Huh? I've never heard of that problem before. What is it? Read me the entire description of the problem so I can write it on the board.'' The problem was as follows:
Input: A finite set X of variables, two programs 
and 
, each a sequence
of assignments of the form
where the 
are in X; and a value set V.
Output: Is there an initial assignment of a value from V to each variable in X such that the two programs yield different final values for some variable in X?
I looked at my watch. Ten minutes to go. But now everything was on the table. I was faced with a language problem. The input was two programs with variables, and I had to test to see whether they always do the same thing.
``First things first. We need to select a source problem for our reduction. Do we start with integer partition? 3-satisfiability? Vertex cover or Hamiltonian path?''
Since I had an audience, I tried thinking out loud.
``Our target is not a graph problem or a numerical problem,
so let's start thinking about the old reliable: 3-satisfiability.
There seem to be some similarities.
3-SAT has variables.
This thing has variables.
To be more like 3-SAT, we could try limiting the variables in this problem
so they only take on two values, i.e. 
.
Yes. That seems convenient.''
My watch said nine minutes left. ``So, class, which way does the reduction go. 3-SAT to language or language to 3-SAT?''
The front row correctly murmured, ``3-SAT to language.''
``Right. So we have to translate our set of clauses into two programs. How can we do that? We can try to split the clauses into two sets and write separate programs for each of them. But how do we split them? I don't see any natural way how to do it, because eliminating any single clause from the problem might suddenly make an unsatisfiable formula satisfiable, thus completely changing the answer. Instead, let's try something else. We can translate all the clauses into one program, and then make the second program be trivial. For example, the second program might ignore the input and always outputs either only true or only false. This sounds better. Much better.''
I was still talking out loud to myself, which wasn't that unusual. But I had people listening to me, which was.
``Now, how can we turn a set of clauses into a program?
We want to know whether the set of clauses can be satisfied,
or if there is an assignment of the variables such that it is true.
Suppose we constructed a program to evaluate
whether 
is satisfied.
We can do it like this ....''
It took me a few minutes worth of scratching before I found
the right program.
I assumed that I had access to constants for 
and 
,
which seemed
reasonable, in the sense that it shouldn't make the
problem algorithmically harder.
Once my proof worked, I could later worry about removing the extra assumption
if desired.
``Great. Now I have a way to evaluate the truth of each clause. I can do the same thing to evaluate whether all the clauses are satisfied.''
Now the back of the classroom was getting excited. They were starting to see a ray of hope that they would get to leave on time. There were two minutes left in class.
``Great.
So now we have a program that can evaluate to be true if and only if
there is a way to assign the variables so as to satisfy the set of clauses.
We need a second program to finish the job.
What about 
?
Yes, that is all we need.
Our language problem asks whether the two programs
always output the
same thing, regardless of the possible variable assignments.
If the clauses are satisfiable, that means that there must be an assignment
of the variables such that the long program would output true.
Testing whether the programs are equivalent is exactly the same as asking
if the clauses are satisfiable.''
I lifted my arms in triumph. ``And so, the problem is neat, sweet, and NP-complete.'' I got the last word out just before the bell rang.
This exercise was so much fun that I repeated it the next time I taught the course, using a different randomly selected problem. The audio from my ultimately successful attempt to prove hardness is accessible from the CD-ROM, if you want to hear what the creation of an NP-completeness proof sounds like.
