← notes

reductions

Turing reductions.

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 Y

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?