reductions
Turing reductions.
To prove a statement, we want to reduce problem Y to problem X.
in other words, if we had a black box that can solve instances of problem X, how can you solve any instance of Y using a polynomial number of steps, plus a polynomial number of calls to the black box that solves X?
Reductions
We know Y is NP-complete, and we want to show X is also NP-complete. in other words, we want to show X is at least as hard as problem YTo prove a statement, we want to reduce problem Y to problem X.
in other words, if we had a black box that can solve instances of problem X, how can you solve any instance of Y using a polynomial number of steps, plus a polynomial number of calls to the black box that solves X?