NP-Completeness Problem A is NP-complete if Problem a is in NP 2. For any Problem A'in NP, a'is reducible to a in polynomial time Class NPC: The class of all NP-complete problems, which is a subclass of NP 8 the hardest problems in NP Solve a problem in NPC, you can solve ALL problems in NPNP-Completeness Problem A is NP-complete if 1. Problem A is in NP 2. For any Problem A’ in NP, A’ is reducible to A in polynomial time • Class NPC: The class of all NP-complete problems, which is a subclass of NP ❖ The hardest problems in NP ❖ Solve a problem in NPC, you can solve ALL problems in NP 13