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.
It can be shown that (SAT, ε-UNSAT) characterizes PCP(O(log n), O(1)).
L
∈
PCP
(
O
(
log
n
)
,
O
(
1
)
)
, then
L
≤
(
SAT
,
ϵ
−
UNSAT
)
. (See PCP theorem for more information)
Let each bit in the proof y be
y
1
,
y
2
,
…
,
y
m
.
First, it is necessary to encode when the verifier accepts in 3CNF clauses
ϕ
=
⋀
r
ϕ
r
. Next, for each random string r, construct a sub-formula
ϕ
r
. For a fixed r, its possible to determine all the variables queried, Enumerate each random string r, and add a clause
ϕ
r
=
f
r
(
y
i
1
,
y
i
2
,
…
,
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
∈
L
, then there is a proof y such that is accepted for every random string r. Therefore,
ϕ
(
y
1
,
y
2
,
…
,
y
m
)
is satisfiable.
If
x
∉
L
, then for every assignment to
y
1
,
y
2
,
…
,
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
ϵ
=
1
2
q
2
q
fraction of the clauses fail.
Therefore,
L
≤
(
SAT
,
ϵ
−
UNSAT
)
.
For
(
S
A
T
,
ϵ
−
U
N
S
A
T
)
∈
P
C
P
(
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
/
ϵ
)
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
/
ϵ
)
=
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
/
ϵ
)
=
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
(
1
−
ϵ
)
1
/
ϵ
≤
1
/
e
<
1
/
2
. Therefore,
(
S
A
T
,
ϵ
−
U
N
S
A
T
)
∈
P
C
P
(
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)).
