Concepts of Completeness and NP• Utility of relative classification results– Consider only a pair of problems Π and Π0∗ What does Π0≤pΠ mean?· This means that if Π ∈ P, then Π0∈ P.· Intuitively, Π is at least as hard as Π0∗ What does Π ≤pΠ0and Π0≤pΠ mean?· This means that if either Π or Π0are in P, then the other one is as well.· Intuitively, these two problems are equivalent in difficulty.∗ In isolation, these results have relatively little impact unless you care aboutthese two specific problems– Consider a set of problems C∗ What does ∀Π0∈ C, Π0≤pΠ mean?· This means that if Π is in P, then all the problems in C are in P.· Intuitively, Π is the “hardest” problem in the set of problems {Π} ∪ C∗ What does ∀Π, Π0∈ C, Π ≤pΠ0mean?· If any one of the problem in the set C is in P, then they all are.· Intuitively, the problems in C are “equivalent” in difficulty.∗ The importance of these results really depends on the class C• Definition of C-complete and C-hard– Let C be a set of problems– C-hard∗ A problem Π is C-hard if ∀Π0∈ C, Π0≤pΠ holds.∗ That is, Π is in P if and only if all of C is.– C-complete∗ A problem Π is C-complete if Π is C-hard and Π ∈ C.∗ That is, Π is in C and is the “hardest” problem in C (with respect to beingin P)• Observations about C-complete and C-hard– All C-complete problems are equivalent in difficulty with respect to being in P– Proving a new problem Π is C-hard∗ If there is a known C-complete problem Π0, then we can prove Π is C-hard byshowing that Π0≤pΠ· This follows from transitivity of polynomial-time many-one reductions∗ If there is no known C-complete problem Π0, we require some method forproving that all problems in C polynomial-time many-one reduce to Π.1• Polynomial-time many-one reductions are transitiveThat is, if Π1≤pΠ2and Π2≤pΠ3, then Π1≤pΠ3,• Proof– Let R1be the reduction used to prove Π1≤pΠ2– Let R2be the reduction used to prove Π2≤pΠ3– Let x be an input to Π1– Define R3(x) to be R2(R1(x))– Argument that R3(x) is a yes input to Π3if and only if x is a yes input to Π1∗ Because R1is a reduction between Π1and Π2, we know that R1(x) is a yesinput to Π2if and only if x is a yes input to Π1∗ Because R2is a reduction between Π2and Π3, we know that R2(R1(x)) is ayes input to Π3if and only if R2(R1(x)) is a yes input to Π2∗ Applying transitivity of if and only if, we get the desired relationship thatR3(x) is a yes input to Π3if and only if x is a yes input to Π1– Argument that R3is polynomial-time computable∗ Let R1take time nc1∗ Let R2take time nc2∗ Let n be the size of x∗ Then the R1portion of R3takes time nc1∗ Furthermore, R1(x) has size at most max(n, nc1).∗ Therefore, the R2portion of R3takes time at most max(nc2, (nc1)c2) = max(nc2, nc1c2)∗ In either case, the total time taken by R3is polynomial in n2• A potentially interesting C to consider is the class NP bec ause– It includes many interesting problems– It seems unlikely it is identical to P– We can show many interesting problems have the above property of being NP-complete• NP-hard and NP-complete– A problem Π is NP-hard if ∀Π0∈ NP, Π0≤pΠ– A problem Π is NP-complete if∗ Π ∈ NP.∗ Π is NP-hard.– Proving a problem Π is NP-complete.1. Show Π ∈ NP∗ Usually the easy step2. Prove for all Π0∈ NP, Π0≤pΠ.∗ Table method, simulation-based method: Cook’s Theorem∗ Show that Π0≤pΠ where Π0is a known NP-hard problem.• The importance of NP-completeness and the “Is P = NP?” question.– Practioner’s point of view∗ There exist a large number of interesting and seemingly different problemswhich have been proven to be NP-complete∗ The P = NP question represents the question of whether or not all of thesedifferent and interesting problems belong to P∗ As the set of NP-complete problems increases, the question becomes moreinteresting and important– Theoretician’s point of view∗ We will show later that NP is exactly the set of problems which can be verifiedin polynomial time.∗ Thus “Is P = NP?” can be rephrased as follows.· Is it true that any problem which can be “verified” in polynomial time canbe “solved” in polynomial time?– Hardness implications∗ It seems unlikely that the problems which can be verified in polynomial timealso can be solved in polynomial time.∗ If you believe that, this implies that P 6= NP.∗ Thus, proving a problem to be NP-complete is a hardness result.3• Complexity class NP– Definitions∗ Let Π be a decision problem∗ Let I be an input instance for Π∗ Let Y (Π) be the set of yes input instances∗ Let N(Π) be the set of no input instances∗ Let C(I) be a “certificate” that instance I ∈ Y (Π).– P is the set of problems that can be solved in polynomial time.∗ If Π is in P, there exists an algorithm that when given I can determine if I isa yes input instance in polynomial time.– Informal: NP is the set of problems that can be verified in polynomial time.– More formal: If Π is in NP, then there exists an algorithm A with the followingproperties:∗ For all I ∈ Y (Π), there exists a polynomial-sized certificate C(I) such thatA(I, C(I)) = yes.∗ For all I ∈ N(Π), for all polynomial-sized certificates C(I), A(I, C(I)) = no.∗ Furthermore, A runs in polynomial-time.– Example: Independent Set problem∗ Certificate: a candidate independent set C∗ Algorithm: Check to see if C is an independent set of size K· For any input I that is a yes input instance, there does exist a C such thatA(I, C(I)) will return yes.· For any input I that is a no input instance, there does NOT exist a C suchthat A(I, C(I)) will ever return yes.– Certificates and Verification Algorithms∗ In most cases, you can think of the certificate C(I) as a candidate solution forinput instance I.∗ For example, in the independent set problem, the certificate was a candidateindependent set.∗ In this case, the verification algorithm simply verifies that C(I) is a true solu-tion for I.∗ For yes input instances, such a candidate solution will exist.∗ For no input instances, no such candidate solution can exist.– Proving a problem is in NP∗ You need to describe what certificate C(I) will be for any input instance I.∗ You need to describe the verification algorithm (usually