Reducing a Problem to another
A problem Q can be reduced to another problem Q’ if any instance of Q can be “easily rephrased” as an instance of Q’.
A Language L1 is polynomial time reducible to a language L2 written as L1≤pL2, if there exists a polynomial time computable function f : {0,1}* {0,1}* such that x Є L1 if and only if f(x) Є L2
We call the function f as reduction function and the polynomial time algorithm F that computes f is called reduction algorithm