2-SAT is a restricted form of the Boolean satisfiability problem in which each clause contains at most two literals. A literal is a Boolean variable or its negation, and a satisfying assignment gives every variable a truth value that makes the entire formula true. Unlike unrestricted Boolean satisfiability, 2-SAT has a linear-time solution: its clauses can be represented as implications, and satisfiability can be determined by examining cycles in a directed graph. It is an important example in computational complexity of how a small restriction on the form of an input can change a problem’s difficulty.
Definition and notation
A formula is in conjunctive normal form (CNF) if it is a conjunction of clauses, each of which is a disjunction of literals. A 2-CNF formula has the form
where each and is a literal drawn from variables . The operators , , and mean AND, OR, and NOT, respectively.
For example,
is a 2-CNF formula. The assignment , , and satisfies all three clauses.
Definitions commonly allow clauses with at most two literals. If exactly two literal positions are required, a unit clause can be written as . An empty clause is always false, so a formula containing one is immediately unsatisfiable. A formula with no clauses is true under every assignment.
The decision version asks only whether a satisfying assignment exists. A constructive version also returns one. Both can be solved in linear time.
The term “2-SAT” refers to the number of literals per clause, not to the total number of variables or the number of values a variable can take.
Implication graph
The central observation is the logical equivalence
If is false, must be true; if is false, must be true.
The implication graph is a directed graph with one vertex for each literal and . Each clause contributes two directed edges:
Thus, a formula with variables and two-literal clauses produces vertices and at most edges before duplicate removal.
A path from a literal to a literal means that setting true forces true through successive implications. Every edge also has a paired contrapositive edge: if appears, so does .
A unit clause can be represented by the edge . A tautological clause such as imposes no restriction.
Satisfiability criterion
A strongly connected component (SCC) is a maximal set of vertices in which every vertex can reach every other vertex by a directed path.
The fundamental criterion is:
A 2-CNF formula is satisfiable if and only if no variable and its negation belong to the same strongly connected component of its implication graph.
Equivalently,
Why a contradictory component implies unsatisfiability
If and lie in the same component, there are paths
Setting true forces true. Setting false makes true, which forces true. Neither choice is consistent.
For example,
is unsatisfiable. The first two clauses require to be true, while the last two require it to be false.
Why the absence of contradictory components is sufficient
Contracting every SCC to a single vertex produces the condensation graph, which is a directed acyclic graph. Complementing all literals in one component produces another component, with the directions of corresponding implications reversed. When the formula passes the criterion, these complementary components are distinct.
Take a topological ordering of the condensation graph, numbered so that every edge between distinct components goes from a smaller number to a larger number. Let be the number assigned to the component containing literal . Set
This assignment satisfies every implication. To see why, suppose an edge had a true source and a false destination. Its paired edge is , so the ordering would require
an impossibility. Hence no clause can have both its literals false.
Linear-time algorithm
The standard algorithm proceeds as follows:
- Construct the implication graph.
- Compute its strongly connected components.
- Reject the formula if any variable shares a component with its negation.
- Otherwise, obtain a satisfying assignment from an appropriate ordering of the components.
SCCs can be computed by Tarjan’s algorithm or Kosaraju’s algorithm, both based on depth-first search. With adjacency-list storage, the overall time complexity and space complexity are
Implementations must distinguish a topological order from the incidental numbers assigned by an SCC routine. Some routines number components in reverse topological order; consequently, the comparison used to extract truth values depends on the numbering convention.
A classic linear-time algorithm for formulas with two literals per clause was published by Bengt Aspvall, Michael Plass, and Robert Tarjan in 1979.
Expressing constraints
Many constraints involving two Boolean choices can be translated directly into 2-CNF.
| Constraint | 2-CNF encoding |
|---|---|
| If , then | |
| At least one of | |
| At most one of | |
| Exactly one of | |
| and have equal values | |
| and have different values |
More generally, forbidding one particular joint assignment to two Boolean variables requires just one clause. For example, forbidding together with gives . Any Boolean relation involving at most two variables can therefore be expressed by excluding its forbidden assignments.
Applications
This encoding makes 2-SAT useful for binary-choice feasibility problems:
- Configuration: options may imply other options or be mutually incompatible.
- Restricted scheduling: each item has two possible placements, and incompatible pairs of placements are forbidden.
- Geometric labeling: each label has two candidate positions, and overlapping pairs cannot both be selected.
- Program analysis and verification: some systems of Boolean implications can be solved as 2-SAT instances within broader formal verification procedures.
The restriction is essential. A scheduling or configuration problem is not automatically a 2-SAT problem merely because it contains Boolean decisions; all required constraints must admit a suitable encoding.
Complexity and related problems
Comparison with general SAT
Unrestricted SAT and 3-SAT are NP-complete, whereas 2-SAT is solvable in polynomial time and, more specifically, linear time in its explicit input size. Allowing a third literal per clause therefore crosses an important complexity boundary.
This does not mean every clause of length three can be converted into an equivalent 2-SAT construction by introducing auxiliary variables. A general polynomial-time reduction of 3-SAT to 2-SAT would imply a positive resolution of the P versus NP problem.
At a finer level, 2-SAT is complete for NL, the class of decision problems solvable with nondeterministic logarithmic workspace, under logarithmic-space many-one reductions. This classification concerns memory-limited computation and is compatible with its linear-time algorithms.
Counting satisfying assignments
#2-SAT asks how many satisfying assignments a 2-CNF formula has. It is #P-complete, despite the tractability of deciding whether at least one assignment exists.
The distinction can be seen through independent sets in an undirected graph. Introduce a variable for each vertex and, for every edge , add
Satisfying assignments correspond exactly to vertex subsets containing no adjacent pair. Counting those subsets is a hard counting problem, even though the formula is always satisfiable by setting every variable false.
Maximization and additional requirements
MAX-2-SAT asks for an assignment satisfying as many clauses as possible. Unlike ordinary 2-SAT, it is NP-hard.
Additional requirements can likewise destroy tractability. For example, maximizing the number of true variables in the independent-set encoding is exactly the maximum independent set problem. The linear-time satisfiability algorithm therefore does not automatically extend to optimization over satisfying assignments.
Structural limitations
2-CNF formulas describe a special family of Boolean relations, often called bijunctive relations. Their satisfying assignments are closed under coordinatewise majority: taking three satisfying assignments and choosing, for each variable, the value occurring in at least two of them yields another satisfying assignment.
For a two-literal clause, if the majority assignment made both literals false, each literal would be false in at least two of the three original assignments. Those two sets of assignments must overlap, so at least one original assignment would also falsify both literals—a contradiction.
This property explains an expressive limitation. The relation
is not majority-closed: assignments , , and satisfy it, but their coordinatewise majority, , does not. Consequently, this three-way “at least one” relation cannot be represented exactly by a 2-CNF formula, even with existentially quantified auxiliary variables. Existentially eliminating variables preserves majority closure.