(SAT, ε-UNSAT)

From Wikipedia, the free encyclopedia
  (Redirected from (SAT, e-UNSAT))
Jump to: navigation, search

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[edit]

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

, then . (See PCP theorem for more information)
Let each bit in the proof y be .

First, it is necessary to encode when the verifier accepts in 3CNF clauses . Next, for each random string r, construct a sub-formula . For a fixed r, its possible to determine all the variables queried, Enumerate each random string r, and add a clause , where is true if and only if the PCP system accepts on reading the given random bits r. There are at most SAT clauses. After these clauses are converted into 3CNF clauses, there are at most clauses.

If , then there is a proof y such that is accepted for every random string r. Therefore, is satisfiable.
If , then for every assignment to 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 fails. Therefore, at least fraction of the clauses fail.

Therefore, .

For , let the proof that the PCP system reads be a satisfying assignment for the input 3-CNF, Φ. The system chooses clauses of the proof to check if they are truly satisfied. Note that only random bits are needed to choose one of clauses, and thus only 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 (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 . Therefore, .

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