Reductions Reduction:a transformation between instance a of Problem A and instance B 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 B is also "YES" 10Reductions 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