Friday, November 18, 2005

PCPs, gaps, and hardness factors

I just wanted to go over one more time the connection between PCPs, gaps, and hardness factors. It took a while for me to "get" this myself when I learned it, so I think it bears repeating. Also I hope it will help with understanding questions #1 and #4 on the homework.

1. Let Phi be a class of predicates; e.g., Phi = 3-variable-linear-equations-mod-2, or Phi = Majorities-of-3-literals, or Phi = ORs-of-3-literals. Then the following statements are exactly equivalent:

(a) "Every problem in NP has a PCP with completeness c, soundness s, and a verifier using predicates from Phi."
(b) "3-Colorability has a PCP with completeness c, soundness s, and a verifier using predicates from Phi."
(c) "Gap-Max-Phi_{c, s} is NP-hard."
(d) "There is a polynomial time reduction which, given a graph G, spits out M many tests from Phi over a bunch of "variables", such that (i) if G is 3-colorable, then there is an assignment to the variables satisfying at least cM of the tests; (ii) if G is not 3-colorable, then every assignment to the variables satisfies fewer than sM of the tests."

(a) <=> (b) is just because 3-Colorability is NP-complete, and polynomial-time reductions can be "built into" PCP systems.

(c) <=> (d) is just because (d) is really the definition of (c).

(b) <=> (d) involves some thought about what the definitions mean. "Indices of proof positions" in (b) correspond to "variables" in (d); "proofs" in (b) correspond to "assignments" in (d); and "picking a random test and understand the probability that it passes" in (b) corresponds to "writing down all the tests and counting how many of them are satisfied" in (d).

------------------------------

2. Further, the statement (c) "Gap-Max-Phi_{c,s} is NP-hard" implies (but is *not* equivalent to) the statement
(e) "There is no poly-time (s/c)-approximation algorithm for the Max-Phi problem unless P = NP."

Proof of (c) => (e): Suppose (c) is true, and further suppose that there *is* a polynomial-time algorithm A which, when given as input M tests from Phi over variables, always outputs an assignment satisfying at least an s/c fraction of whatever the optimum assignment satisfies. We will show that the existence of this algorithm A means that 3-Colorability is solvable in polynomial time, and hence P = NP.

So why is 3-Colorability in polynomial time in this case? Here is the polynomial time algorithm B which solves 3-Colorability:

  • Given a graph G, run the reduction guaranteed by statement (c); this spits out a list of M many tests from Phi.
  • Run algorithm A on this list of tests, producing some assignment alpha to the variables.
  • Check if alpha satsifies at least sM of the tests. If so, output "YES, G is 3-colorable." If not, output "NO, G is not 3-colorable."

Since the reduction guaranteed by (c) is polynomial time, and A is polynomial time, the overall algorithm B is polynomial time. Why is it correct? If the input graph G is 3-colorable, then the reduction guaranteed by (c) spits out a list of M tests with the guarantee that there is an assignment satisfying at least cM of them. I.e., the optimal assignment gives at least cM. Thus by the guarantee of the supposed approximation algorithm A, it will return an assignment alpha satisfying at least (s/c) * (cM) = sM tests. Thus B will correctly say "YES". On the other hand, if G was not 3-colorable, then the reduction guaranteed by (c) will spit out a list where *every* assignment to the variables satisfies fewer than sM of the tests. In this case, no matter what assignment A outputs, there's no way it will satisfy as many as sM tests; hence B will correctly output "NO".

0 Comments:

Post a Comment

<< Home