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.