Reductions Reduction: a transformation between instance a of Problem a and instance p of problem b such that The transformation takes polynomial time polynomial in size of the input instance The answer for a is yES"if and only if the answer forβ is also"Es"Reductions Reduction: a transformation between instance α of Problem A and instance β of Problem B such that • The transformation takes polynomial time ❖ Polynomial in size of the input instance • The answer for α is “YES” if and only if the answer for β is also “YES” 10