Lukas' Notes

Definition

2-SAT4 Satisfiability Decision Problem

Instance: A Boolean formula in conjunctive normal form satisfying

where counts the literals in clause . The bound is fixed, not part of the input; the exceptional clauses may have arbitrary length.

Question: Does there exist a truth assignment with ?

Equivalently, the allowed inputs become 2-SAT formulas after deleting at most four clauses. Satisfiability is still required for the entire original formula, including those clauses.