December 3, 200131 Reduction Example Reduction is a general technique for showing that one problem is harder (easier) than another For problems A and B, we can often show: if A can be solved efficiently, then so can B In this case, we say B reduces to A (B is easier than A, or, B cannot be worse than A)
{}