MAX-3SAT - Theorem 2

Theorem 2

Håstad demonstrates a tighter result than Theorem 1 i.e. the best known value for ε.

He constructs a PCP Verifier for 3-SAT that reads only 3 bits from the Proof.

For every ε > 0, there is a PCP-verifier M for 3-SAT that reads a random string r of length O(log(n)) and computes query positions i_r, j_r, k_r in the proof π and a bit b_r. It accepts if and only if

π(i_r) ⊕ π(j_r) ⊕ π(k_r) ⊕ = b_r.

The Verifier has completeness (1-ε) and soundness 1/2 + ε (refer to PCP (complexity)). The Verifier satisfies

If the first of these two equations were equated to "=1" as usual, one could find a proof π by solving a system of linear equations (see MAX-3LIN-EQN) implying P = NP.

• If z ∈ L, a fraction ≥ (1- ε) of clauses are satisfied.
• If z ∉ L, then for a (1/2- ε) fraction of R, 1/4 clauses are contradicted.

This is enough to prove the hardness of approximation ratio