Now that both satisfiability and 3-SAT are known to be hard, we can use either of them in reductions. What follows are a pair of more complicated reductions, designed to serve both as examples for how to proceed and to increase our repertoire of known hard problems from which we can start. Many reductions are quite intricate, because we are essentially programming one problem in the language of a significantly different problem.

One perpetual point of confusion is getting
the direction of the reduction right.
Recall that we must transform *every* instance of a
known NP-complete problem into an
instance of the problem we are interested in.
If we perform the reduction the other way,
all we get is a slow way to solve the
problem of interest,
by using a subroutine that takes exponential time.
This always is confusing at first, for this direction of reduction
seems bass-ackwards.
Check to make sure you understand the direction of reduction now, and think
back to this whenever you get confused.

Mon Jun 2 23:33:50 EDT 1997