(SAT, ε-UNSAT)

In computational complexity theory, (SAT, ε-UNSAT) is a language that is used in the proof of the PCP theorem, which relates the language NP to probabilistically checkable proof systems.

For a given 3-CNF formula, Φ, and a constant, ε < 1, Φ is in (SAT, ε-UNSAT) if it is satisfiable and not in (SAT, ε-UNSAT) if the maximum number of satisfiable clauses (MAX-3SAT) is less than or equal to (1-ε) times the number of clauses in Φ. If neither of these conditions are true, the membership of Φ in (SAT, ε-UNSAT) is undefined.

Complexity

It can be shown that (SAT, ε-UNSAT) characterizes PCP(O(log n), O(1)).

[math]\displaystyle{ L \in \mbox{PCP}(O(\log n),O(1)) }[/math], then [math]\displaystyle{ L \le ( \mbox{SAT}, \epsilon-\mbox{UNSAT}) }[/math]. (See PCP theorem for more information)
Let each bit in the proof y be [math]\displaystyle{ y_1, y_2, \ldots, y_m }[/math].

First, it is necessary to encode when the verifier accepts in 3CNF clauses [math]\displaystyle{ \phi=\bigwedge_r \phi_r }[/math]. Next, for each random string r, construct a sub-formula [math]\displaystyle{ \phi_r }[/math]. For a fixed r, its possible to determine all the variables queried, Enumerate each random string r, and add a clause [math]\displaystyle{ \phi_r = f_r (y_{i_1}, y_{i_2}, \ldots , y_{i_q}) \ }[/math], where [math]\displaystyle{ f_r }[/math] is true if and only if the PCP system accepts on reading the given random bits r. There are at most [math]\displaystyle{ 2^q }[/math] SAT clauses. After these clauses are converted into 3CNF clauses, there are at most [math]\displaystyle{ q 2 ^ q }[/math] clauses.

If [math]\displaystyle{ x \in L }[/math], then there is a proof y such that is accepted for every random string r. Therefore, [math]\displaystyle{ \phi(y_1,y_2,\ldots,y_m) }[/math] is satisfiable.
If [math]\displaystyle{ x \notin L }[/math], then for every assignment to [math]\displaystyle{ y_1, y_2, \ldots, y_m }[/math] the corresponding proof causes the verifier to reject for half of the random strings r. For each r that is rejected one of the clauses in [math]\displaystyle{ f_r }[/math] fails. Therefore, at least [math]\displaystyle{ \epsilon = \frac{1}{2 q 2^q} }[/math] fraction of the clauses fail.

Therefore, [math]\displaystyle{ L \le (\mbox{SAT}, \epsilon-\mbox{UNSAT}) }[/math].

For [math]\displaystyle{ (SAT, \epsilon-UNSAT) \in PCP(O(\log n), O(1)) }[/math], let the proof that the PCP system reads be a satisfying assignment for the input 3-CNF, Φ. The system chooses [math]\displaystyle{ O(1/\epsilon) }[/math] clauses of the proof to check if they are truly satisfied. Note that only [math]\displaystyle{ \log n }[/math] random bits are needed to choose one of [math]\displaystyle{ n }[/math] clauses, and thus only [math]\displaystyle{ O(\log n/\epsilon) = O(\log n) }[/math] total random bits are needed. (Remember that ε is a constant.) For each clause to be checked, only 3 bits need to be read, and thus only [math]\displaystyle{ O(3/\epsilon) = O(1) }[/math] (a constant number) of bits from the proof need to be read. The system rejects if any of the clauses are not satisfied. If Φ is satisfiable, then there exists a proof (a truly satisfying assignment) that the system will always accept. If Φ is not in (SAT, ε-UNSAT), this means that an ε fraction of the clauses is not satisfiable. The probability that this system will accept in this case is [math]\displaystyle{ (1-\epsilon)^{1/\epsilon} \leq 1/e \lt 1/2 }[/math]. Therefore, [math]\displaystyle{ (SAT, \epsilon-UNSAT) \in PCP(O(\log n), O(1)) }[/math].

(SAT, ε-UNSAT) is an NP-hard language. As part of the proof of the PCP theorem, (SAT, ε-UNSAT) has also been shown to be in PCP(O(log n), O(1)).