Proof of Np-Completeness Given a problem a, prove that a is Np-complete Proof scheme 1 Show Problem A is in NP(easier part) For all Problems in NP, reduce them to a in polynomial time 8 This has been done for 3SAT, the first NP-complete problem Proof scheme 2 Show Problem A is in NP (easier part) For arbitrary problem A'in NPC, reduce A' to A in polynomial time .s This would be much easierProof of NP-Completeness Given a Problem A, prove that A is NP-complete Proof Scheme 1 • Show Problem A is in NP (easier part) • For all Problems in NP, reduce them to A in polynomial time ❖ This has been done for 3SAT, the first NP-complete problem Proof Scheme 2 • Show Problem A is in NP (easier part) • For arbitrary problem A’ in NPC, reduce A’ to A in polynomial time ❖ This would be much easier 15