next up previous contents index CD CD Algorithms
Next: Integer Programming Up: Intractable Problems and Approximations Previous: 3-Satisfiability

Difficult Reductions

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