(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)). formula_1, then formula_2. (See PCP theorem for more information) Let each bit in the proof "y" be formula_3. First, it is necessary to encode when the verifier accepts in 3CNF clauses formula_4. Next, for each random string "r", construct a sub-formula formula_5. For a fixed "r", its possible to determine all the variables queried, Enumerate each random string "r", and add a clause formula_6, where formula_7 is true if and only if the PCP system accepts on reading the given random bits "r". There  are at most formula_8 SAT clauses. After these clauses are converted into 3CNF clauses, there are at most formula_9 clauses. If formula_10, then there is a proof "y" such that is accepted for every random string "r". Therefore, formula_11 is satisfiable. If formula_12, then for every assignment to formula_13 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 formula_7 fails. Therefore, at least formula_15 fraction of the clauses fail. Therefore, formula_16. For formula_17, let the proof that the PCP system reads be a  satisfying assignment for the input 3-CNF, Φ. The system chooses formula_18 clauses of the proof to check if they are truly satisfied. Note that only formula_19 random bits are needed to choose one of formula_20 clauses, and thus only formula_21 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 formula_22 (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 formula_23. Therefore, formula_17. (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)).