1SAT
1SAT is the decision problem of determining satisfiability for formulas in which each clause contains exactly one literal, i.e., a conjunction of unit clauses. Such a formula specifies a set of constraints where each constraint requires a particular variable to be true or false. Examples of clauses are x and ¬y; a formula might require x to be true and y to be false simultaneously.
The problem is in P and, in fact, can be solved in linear time in the size
A standard algorithm processes the list of unit clauses one by one. It maintains a mapping from
- if the literal is x, the algorithm requires x to be true; if x was previously assigned
- if the literal is ¬x, the algorithm requires x to be false; if x was previously assigned
Duplicate literals and repeated constraints are harmless. If the end of the input is reached without a
1SAT is a special case of CNF-SAT and a trivial subset of 2-SAT. It illustrates unit propagation