# (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)).

${\displaystyle L\in {\mbox{PCP}}(O(\log n),O(1))}$, then ${\displaystyle L\leq ({\mbox{SAT}},\epsilon -{\mbox{UNSAT}})}$. (See PCP theorem for more information)
Let each bit in the proof y be ${\displaystyle y_{1},y_{2},\ldots ,y_{m}}$.

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

If ${\displaystyle x\in L}$, then there is a proof y such that is accepted for every random string r. Therefore, ${\displaystyle \phi (y_{1},y_{2},\ldots ,y_{m})}$ is satisfiable.
If ${\displaystyle x\notin L}$, then for every assignment to ${\displaystyle y_{1},y_{2},\ldots ,y_{m}}$ 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 ${\displaystyle f_{r}}$ fails. Therefore, at least ${\displaystyle \epsilon ={\frac {1}{2q2^{q}}}}$ fraction of the clauses fail.

Therefore, ${\displaystyle L\leq ({\mbox{SAT}},\epsilon -{\mbox{UNSAT}})}$.

For ${\displaystyle (SAT,\epsilon -UNSAT)\in PCP(O(\log n),O(1))}$, let the proof that the PCP system reads be a satisfying assignment for the input 3-CNF, Φ. The system chooses ${\displaystyle O(1/\epsilon )}$ clauses of the proof to check if they are truly satisfied. Note that only ${\displaystyle \log n}$ random bits are needed to choose one of ${\displaystyle n}$ clauses, and thus only ${\displaystyle O(\log n/\epsilon )=O(\log n)}$ 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 ${\displaystyle O(3/\epsilon )=O(1)}$ (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 ${\displaystyle (1-\epsilon )^{1/\epsilon }\leq 1/e<1/2}$. Therefore, ${\displaystyle (SAT,\epsilon -UNSAT)\in PCP(O(\log n),O(1))}$.

(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)).