Recap: The PCP Theorem by Gap Amplification
The PCP theorem (almost) states this surprising property that given a proof of answer of some YES/NO problem, there is some scheme that checks just some constant pieces of the proof and decides whether the proof is correct or not, and this decision is with high probability a correct decision.
It is almost easily known that NP-hardness of GAP-3SAT problem is equivalent to correctness of PCP theorem where GAP-3SAT is the following problem: given a 3-SAT formula and a real number c, whether the formula is satisfiable or under every truth assignment at least c fraction of clauses remain unsatisfied. It is obvious that for small values of c this problem is NP-hard (since it is just SAT for small c), so the difficult question is the case of larger c values. Arora and Safra established a proof of PCP theorem which was long and algebraic. This paper presents a more combinatorial proof using reduction of a variant of GAP-3SAT for small values of c to the same variant of GAP-3SAT for larger values (actually constant values) of c. The variant of 3SAT is this: given a graph where each vertex of graph is a variable over a finite alphabet and each edge is a relation over that alphabet, and given a real value c, whether there is satisfying assignment to the vertices of the graph or always c fraction of edges remain unsatisfied.
The tool to prove this, is almost a standard approach: first we convert the graph to an expander using replacement and graph superimposition (union of a graph with an expander). Then using powering (an operation similar to zigzag product) we increase the "expansion" in the graph and it turns out that this increases the fraction of unsatisfied edges. In the last step using a technical method we decrease the size of the alphabet of the graph (which the powering operation increases that by an exponential factor). All these operations can be done in polytime and as a result the farction of unsatisfied edges double. If we repeat these steps for a logarithmic number of times, the fraction of unsatisfied edges becomes as large as a constant, which is the desired property.
It is almost easily known that NP-hardness of GAP-3SAT problem is equivalent to correctness of PCP theorem where GAP-3SAT is the following problem: given a 3-SAT formula and a real number c, whether the formula is satisfiable or under every truth assignment at least c fraction of clauses remain unsatisfied. It is obvious that for small values of c this problem is NP-hard (since it is just SAT for small c), so the difficult question is the case of larger c values. Arora and Safra established a proof of PCP theorem which was long and algebraic. This paper presents a more combinatorial proof using reduction of a variant of GAP-3SAT for small values of c to the same variant of GAP-3SAT for larger values (actually constant values) of c. The variant of 3SAT is this: given a graph where each vertex of graph is a variable over a finite alphabet and each edge is a relation over that alphabet, and given a real value c, whether there is satisfying assignment to the vertices of the graph or always c fraction of edges remain unsatisfied.
The tool to prove this, is almost a standard approach: first we convert the graph to an expander using replacement and graph superimposition (union of a graph with an expander). Then using powering (an operation similar to zigzag product) we increase the "expansion" in the graph and it turns out that this increases the fraction of unsatisfied edges. In the last step using a technical method we decrease the size of the alphabet of the graph (which the powering operation increases that by an exponential factor). All these operations can be done in polytime and as a result the farction of unsatisfied edges double. If we repeat these steps for a logarithmic number of times, the fraction of unsatisfied edges becomes as large as a constant, which is the desired property.
posted by reza at
7:19 PM
0 Comments:
Post a Comment
<< Home