Two Ways to Use Reductions Suppose problem a is reducible to problem B Solve problem If there exists efficient algorithm for problem b, then we can solve Problem A efficiently Prove hardness &o If Problem a is hard, then problem b is also hard Efficient algorithms Problem a Reduction Problem b HardnessTwo Ways to Use Reductions Suppose Problem A is reducible to Problem B • Solve problem ❖ If there exists efficient algorithm for Problem B, then we can solve Problem A efficiently • Prove Hardness ❖ If Problem A is hard, then Problem B is also hard Problem A Reduction Problem B Efficient algorithms Hardness 12