The PCP theorem implies that there exists an ε > 0 such that (1-ε)-approximation of MAX-3SAT is NP-hard.
For x ∈ L, a 3-CNF formula Ψx is constructed so that The Verifier V reads all required bits at once i.e. makes non-adaptive queries.
We introduce Boolean variables x1,...,xl, where l is the length of the proof.
It can be concluded that if this holds for every NP-complete problem then the PCP theorem must be true.
Håstad [2] 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
and computes query positions ir, jr, kr in the proof π and a bit br.
The Verifier has completeness (1−ε) and soundness 1/2 + ε (refer to PCP (complexity)).
This is enough to prove the hardness of approximation ratio MAX-3SAT(B) is the restricted special case of MAX-3SAT where every variable occurs in at most B clauses.
Before the PCP theorem was proven, Papadimitriou and Yannakakis[3] showed that for some fixed constant B, this problem is MAX SNP-hard.
Moreover, although the decision problem 2SAT is solvable in polynomial time, MAX-2SAT(3) is also APX-hard.
[8] [9] [10] Berman, Karpinski and Scott proved that for the "critical" instances of MAX-3SAT in which each literal occurs exactly twice, and each clause is exactly of size 3, the problem is approximation hard for some constant factor.