Definition 13.6 Polynomial reduction and reducibility
Let T be a function from the input set for a decision problem P into the input set for a decision problem Q. T is a polynomial reduction (also called a polynomially transformation) from P to Q if all of the following hold:
1. T can be computed in polynomially bounded time.
2. For every string x, if x is a yes input for P, then T(x) is a yes input for Q.
3. For every string x, if x is a no input for P, then T(x) is a no input for Q.
it is usually easier to prove the contrapositive of part 3.
3'. For every x, if T(x) is a yes input for Q, then x, is a yes input for P.
problem P is polynomially reducible (also called polynomially transformable) to Q if there exists a polynomially transformation from P to Q. (We usually just say P is reducible to Q)
The notation
P \le {_pQ}
is used to indicate that P is reducible to Q.
P \le {_pQ} \iff Q is at least as hard to solve as P.