Reductions es yes Polynomial Time Polynomial Time Reduction Algorithm for Problem B Polynomial Time Algorithm for Problem A If problem a is reducible to problem B in polynomial time, then which problem is easier? A, Or b Problem b is at least as hard as problem aReductions Polynomial Time Reduction Polynomial Time Algorithm for Problem B Polynomial Time Algorithm for Problem A α β Yes No Yes No If problem A is reducible to problem B in polynomial time, then which problem is easier? A Or B ? Problem B is at least as hard as Problem A! 11