Understanding Approximation Algorithms and Probabilistically Checkable Proofs
Explore the world of approximation algorithms and probabilistically checkable proofs in advanced algorithmic studies, delving into NP verification, PCPs, and more to understand complexities in approximating different computational problems.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
CMPT 409/815 Advanced Algorithms November 25, 2020
Hardness of Approximation and Probabilistically Checkable Proofs
Approximation algorithms and inapproximability In this course we saw several approximation algorithms: Vertex-Cover 2-approximation 2- is NP-hard for any >0 Max-3-SAT 7/8-approximation 7/8+ is NP-hard for all >0 Max-Cut 0.878-approximation aGW+ is NP-hard* for all >0 Max-Clique polylog(n)/n-approximation n0.999is NP-hard for any >0 Metric-TSP 1.5-approximation 1.008 is NP-hard Why different problems have different approximation guarantees/inapproximability?
Definition of NP Examples: 3-SAT, max-clique, min-vertex-cover An NP verifier: An NP verifier VL for a language L gets an input x and a proof of length | |=poly(|x|) and works as follows: VL reads x and VL runs in poly(|x|) time, and decides to ACCEPT or REJECT YES case: if x L, then there exists a proof x such that VL(x, x)=ACCEPT NO case: if x L, then for any proof we have VL(x, )=REJECT X What if we allow the verifier to use randomness? The class NP: A language L belongs to NP if L has an NP verifier.
Probabilistically checkable proofs (PCPs) An (r,q)-PCP verifier: An (r,q)- PCP verifier VL for a language L gets an input x and a proof of length | |=poly(|x|) and works as follows: VL reads x VL tosses r random coins, and gets a random string {0,1}r Based on x and the random coins VL reads q coordinates from VL decides to ACCEPT or REJECT YES case: if x L, there exists a proof x such that Pr[VL(x, x)=ACCEPT]=1 NO case: if x L, then for any proof we have Pr[VL(x, )=REJECT] < . X Note that length of is at most | | 2rq.
Probabilistically checkable proofs (PCPs) An (r,q)-PCPc,s verifier: An (r,q)- PCP verifier VL for a language L gets an input x and a proof over the alphabet and works as follows: VL reads x VL tosses r random coins, and gets a random string {0,1}r Based on x and the random coins VL reads q coordinates from VL decided to ACCEPT or REJECT YES case: if x L, there exists a proof x such that Pr[VL(x, x)=ACCEPT] c NO case: if x L, then for any proof we have Pr[VL(x, )=REJECT] s The class PCPc,s[r,q]: A language L belongs to the classPCPc,s[r,q] if L has an (r,q)-PCPc,s verifier.
Probabilistically checkable proofs (PCPs) Let s try a couple of simple examples: 1. What is PCP1,0[r = 0, q = 0]? 2. What is PCP1,0[r = 0, q = 1]? 3. What is PCP1,0[r = 0, q = log(n)]? 4. What is PCP1,0[r = 0, q = poly(n)]? 5. What is PCP1,0.5[r = 1, q = 0]? 6. What is PCP1,0[r = poly(n), q = 0]? 7. What is PCP1,0.5[r = poly(n), q = 0]? 8. What is PCP1,0.5[r = log(n), q = poly(n)]? 9. Prove that PCP1,0.5[r = log(n),q] NP for all 0 q poly(n).
Probabilistically checkable proofs (PCPs) Claim: PCP1,0[r = 0, q = 0] = P. P PCP1,0[r = 0, q = 0] : PCP1,0[r = 0, q = 0] P :
Probabilistically checkable proofs (PCPs) Claim: PCP1,0[r = 0, q = 1] = P. P PCP1,0[r = 0, q = 1] : PCP1,0[r = 0, q = 1] P :
Probabilistically checkable proofs (PCPs) Claim: PCP1,0[r = 0, q = log(n)] = P. P PCP1,0[r = 0, q = log(n)] : PCP1,0[r = 0, q =log(n)] P :
Probabilistically checkable proofs (PCPs) Claim: PCP1,0[r = 0, q = poly(n)] = NP. NP PCP1,0[r = 0, q = log(n)] : PCP1,0[r = 0, q =log(n)] NP :
The PCP Theorem Theorem [AS 92, ALMSS 92]: NP = PCP1,0.5 [r = O(log(n), q = 3]. By repeating the verifier 10 times, the error probability becomes 0.510<0.001 Pretty amazing By reading only random O(1) bits from the proof we can decide if x is in the language or not with high probability. The result was so impressive back then, that New York Times published an article on this.
The PCP Theorem Theorem [AS 92, ALMSS 92]: NP = PCP1,0.5 [r = O(log(n), q = 3].
Probabilistically checkable proofs (PCPs) An (r,q)-PCP verifier: An (r,q)- PCP verifier VL for a language L gets an input x and a proof of length | |=poly(|x|) and works as follows: VL reads x, tosses r random coins, and gets a random string {0,1}r VL reads q coordinates from , and decides to ACCEPT or REJECT YES case: if x L, there exists a proof x such that Pr[VL(x, x)=ACCEPT]=1 NO case: if x L, then for any proof we have Pr[VL(x, )=REJECT] < . X
Constraint satisfaction problems (CSPs) Input n variables (X) over some alphabet , and a collection of constraints (C). Goal: is to find an assignment that satisfies all constraints. Denote by OPT(X,C) the maximal fraction of satisfied constraints. Gap-CSPc,s: Input n variables (X) over some alphabet , and a collection of constraints (C). Goal: distinguish between the following cases YES case: OPT(X,C) c NO case: OPT(X,C) s
Constraint satisfaction problems (CSPs) q-gap-CSPc,s: Input n variables (X) over alphabet , a collection of q-ary constraints (C). Goal: distinguish between the following cases YES case: OPT(X,C) c NO case: OPT(X,C) s Lemma: The following are equivalent: 1. NP PCPc,s[r=O(log(n),q] 2. q-gap-CSPc,s is NP-hard
Constraint satisfaction problems (CSPs) Lemma: The following are equivalent: 1. NP PCPc,s[r=O(log(n),q] 2. q-gap-CSPc,s is NP-hard Proof of 1 2: We want to construct a reduction from SAT to q-gap-CSPc,s. Let be a SAT instance, and let VSAT be the PCP verifier for SAT Consider the proof for VSAT The coordinates of will be the variables of CSP, i.e., number of variables is | | 2rq. Next, for each random string {0,1}r consider the q-are predicate on some q coordinates of . Each such predicate defines a constraint over the variables (coords of ) That is, the CSP has 2r constraints
Constraint satisfaction problems (CSPs) Lemma: The following are equivalent: 1. NP PCPc,s[r=O(log(n),q] 2. q-gap-CSPc,s is NP-hard Proof of 2 1: Suppose that q-gap-CSPc,s is NP-hard. This means that there is a poly time reduction from SAT to q-gap-CSPc,s. Consider the following PCP verifier. Given an instance of sat the verifier runs the reduction and gets the CSP. The proof corresponds to an assignment to the variables Given a proof the verifier chooses a uniformly random constraint, It reads the q coordinate/variables and checks if the constraint is satisfied. YES case and NO case follow from the definition of q-gap-CSPc,s
Questions? Comments?
