Theorem 1 (Inapproximability)
The PCP theorem implies that there exists an ε > 0 such that (1-ε)-approximation of MAX-3SAT is NP-hard.
Proof:
Any NP-complete problem L ∈ PCP(O(log (n)), O(1)) by the PCP theorem. For x ∈ L, a 3-CNF formula Ψx is constructed so that
- x ∈ L ⇒ Ψx is satisfiable
- x ∉ L ⇒ no more than (1-ε)m clauses of Ψx are satisfiable.
The Verifier V reads all required bits at once i.e. makes non-adaptive queries. This is valid because the number of queries remains constant.
- Let q be the number of queries.
- Enumerating all random strings Ri ∈ V, we obtain poly(x) strings since the length of each string r(x) = O(log |x|).
- For each Ri
- V chooses q positions i1,...,iq and a Boolean function fR: {0,1}q->{0,1} and accepts if and only if fR(π(i1,...,iq)). Here π refers to the proof obtained from the Oracle.
Next we try to find a Boolean formula to simulate this. We introduce Boolean variables x1,...,xl, where l is the length of the proof. To demonstrate that the Verifier runs in Probabilistic polynomial-time, we need a correspondence between the number of satisfiable clauses and the probability the Verifier accepts.
- For every R, add clauses representing fR(xi1,...,xiq) using 2q SAT clauses. Clauses of length q are converted to length 3 by adding new (auxiliary) variables e.g. x2 ∨ x10 ∨ x11 ∨ x12 = ( x2 ∨ x10 ∨ yR) ∧ ( ∨ x11 ∨ x12). This requires a maximum of q2q 3-SAT clauses.
- If z ∈ L then
- there is a proof π such that Vπ (z) accepts for every Ri.
- All clauses are satisfied if xi = π(i) and the auxiliary variables are added correctly.
- If input z ∉ L then
- For every assignment to x1,...,xl and yR's, the corresponding proof π(i) = xi causes the Verifier to reject for half of all R ∈ {0,1}r(|z|).
- For each R, one clause representing fR fails.
- Therefore a fraction of clauses fails.
- For every assignment to x1,...,xl and yR's, the corresponding proof π(i) = xi causes the Verifier to reject for half of all R ∈ {0,1}r(|z|).
It can be concluded that if this holds for every NP-complete problem then the PCP theorem must be true.
Read more about this topic: MAX-3SAT
Famous quotes containing the word theorem:
“To insure the adoration of a theorem for any length of time, faith is not enough, a police force is needed as well.”
—Albert Camus (19131960)