(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, &epsilon;-UNSAT) characterizes PCP(O(log n), O(1)).

$L\; in\; mbox\{PCP\}(O(log\; n),O(1))$, then $L\; le\; (\; mbox\{SAT\},\; epsilon-mbox\{UNSAT\})$. (See PCP theorem for more information)
Let each bit in the proof "y" be $y\_1,\; y\_2,\; ldots,\; y\_m$.

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

If $x\; in\; L$, then there is a proof "y" such that is accepted for every random string "r". Therefore $phi(y\_1,y\_2,ldots,y\_m)$ is satisfiable.
If $x\; otin\; L$, then for every assignment to $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 $f\_r$ fails. Therefore at least $epsilon\; =\; frac\{1\}\{2\; q\; 2^q\}$ fraction of the clauses fail.

Therefore $L\; le\; (mbox\{SAT\},\; epsilon-mbox\{UNSAT\})$.

For $(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 $O(1/epsilon)$ clauses of the proof to check if they are truly satisfied. Note that only $log\; n$ random bits are needed to choose one of $n$ clauses, and thus only $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 $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, &epsilon;-UNSAT), this means that an ε fraction of the clauses is not satisfiable. The probability that this system will accept in this case is . Therefore, $(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)).