Supriya Ghosh (Editor)

(SAT, ε UNSAT)

Updated on
Share on FacebookTweet on TwitterShare on LinkedInShare on Reddit
Covid-19

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

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

References

(SAT, ε-UNSAT) Wikipedia


Topics
 
B
i
Link
H2
L