Why two literals change the problem
A clause such as says that whenever is true, must be true. In a formula with at most two literals per clause, every clause can be read as implications between individual literals. Paths in a directed graph then record chains of forced choices. This makes 2-SAT a useful meeting point between satisfiability, graph algorithms, and space complexity.
We will prove a criterion for satisfiability and use it to place the problem in NL. The hardness argument goes in the opposite direction: it translates an arbitrary directed reachability instance into clauses. The result does not say that NL equals L; whether deterministic logarithmic space suffices for 2-SAT is tied to the unresolved L versus NL question.
Formula and graph
Definition 3.6.1
(Literals and 2-CNF formulas)
A literal is a Boolean variable or its negation ; write for the opposite of a literal , so . A 2-CNF formula is a conjunction of clauses, each containing one or two literals. We also permit the empty conjunction, which is true; an explicit empty clause makes the formula false and can be handled separately. Variables are explicitly listed with distinct binary indices, and clauses reference that list; thus the number of variables is at most the input length. Malformed encodings are rejected. Unit clauses are represented as when forming the graph.
Definition 3.6.2
(The implication graph)
For each variable create vertices and . For each clause add edges
The clause is equivalent to both implications. In particular a unit clause contributes .
If a path leads from to , every satisfying assignment making true must also make true. A path of length zero is permitted, although it cannot by itself connect a variable with its distinct negation.
Concept lensStructural
Satisfying assignments as closed sets of literals
An assignment corresponds to its set of true literals, which contains exactly one of for each variable. It satisfies the formula exactly when is closed under the edges: if and the clause is present, then , and symmetrically for . So satisfying assignments are the consistent, successor-closed sets of literals in the implication graph.
Worked example 3.6.3
(Following implications)
Let . The graph includes , followed by . Thus choosing true forces both and . This does not make the formula unsatisfiable: satisfies all clauses. A one-way path from to rules out , not both values of .
The criterion and its proof
Definition 3.6.4
(Strongly connected components and topological order)
Two vertices of a directed graph lie in the same strongly connected component when each reaches the other. Contracting every component to a single vertex gives an acyclic graph, the condensation. A topological ordering of the components lists them so that every edge between distinct components goes from an earlier component to a later one.
Theorem 3.6.5
(The 2-SAT criterion)
A 2-CNF formula with no empty clause is satisfiable if and only if no variable has both a path and a path in its implication graph.
Proof
(Forced values for necessity, component order for sufficiency)
If both paths exist and an assignment satisfies every clause, either or is true. Following the corresponding path forces its opposite true as well, which is impossible. This proves necessity.
For sufficiency, fix a topological ordering of the components. Assign a literal true exactly when the component of occurs later than the component of . The hypothesis ensures that these two components are distinct, so exactly one of and is true and the rule defines an assignment to every variable.
Suppose, toward a contradiction, that a clause is false. Write for the position of the component of literal in the topological ordering. Falsity gives and . The clause edges give and . Together,
an impossibility. Thus every clause is true. This also covers a unit clause written with repeated literals.
Proof X-ray
Where the hypothesis enters and how the chain closes
The hypothesis is used once. Having both paths and means exactly that and share a component, so its failure makes the two positions differ and the rule “the later component is true” well defined. The key move is the chain of inequalities: falsity of the clause contributes two strict steps, and the clause’s own two edges contribute two weak ones, since an edge never points backwards in a topological ordering. The chain returns to , so it asserts . Without the hypothesis the rule has nothing to compare for a literal that shares its component with its negation, as in . Necessity, by contrast, uses neither components nor an ordering: it only follows forced values along paths.
Worked example 3.6.6
(An actual contradiction)
The unit clauses and give edges and . Hence the two literals lie in one strongly connected component and the formula is unsatisfiable. Adding more clauses cannot remove these paths or make the formula satisfiable.
The explorer below builds the implication graph of a 2-CNF formula, reports both path directions for every variable, and checks the component-order assignment clause by clause.
Symmetry of the implication graph and reading off an assignment
The satisfiability criterion says that a 2-CNF formula is satisfiable exactly when no literal shares a strongly connected component with its negation. The construction in that proof depends on the implication graph being symmetric under negation. This section proves that symmetry directly. It then explains why the assignment rule compares complementary components, and why it uses "later" rather than "earlier".
Throughout, write for , so that . A unit clause is read as .
Contraposition is built into the edge set
Lemma 3.6.7
(Edges come in contrapositive pairs)
If is an edge of the implication graph, then is also an edge.
Proof
(Each clause contributes a contrapositive pair)
Every edge comes from some clause , which contributes exactly the two edges and . Suppose is the first of these, so and . Then
which is the second edge from the same clause. The case where is the second edge is symmetric. A unit clause gives , so both edges coincide as . Its contrapositive is , the edge itself. Repeated clauses contribute edges that are already present. Each clause is closed on its own, so the whole edge set is closed.
Corollary 3.6.8
(Path reversal)
If is a path, then so is .
This follows by applying the lemma above to each edge and reading the resulting edges in reverse order. In particular, holds if and only if holds.
Complementary components
For a strongly connected component , define .
Lemma 3.6.9
(The complement of a component is a component)
is a strongly connected component. The map is an involution, and in the condensation if and only if .
Proof
(Reversing paths and maximality)
First, is strongly connected. Take with . Since , path reversal gives , and by the same argument .
Second, is maximal. Let be the component containing . By the first step, is strongly connected, and it contains . Since is a full component, , and therefore . Hence .
The involution property follows from . The reachability statement is path reversal applied to representatives of and .
Two components are either equal or disjoint. So for each , exactly one of two cases holds.
- . Then , and the components pair off.
- . Then every has , which is exactly the unsatisfiable condition. Conversely, if and lie in a common component , then , which forces .
The second case is not excluded by any distinctness assumption. It can occur with a single variable, as the first exercise below shows.
Why the rule compares partners, and why "later"
A topological ordering is only a list of components. It does not by itself say which literals are true. A valid assignment must make exactly one of true, so any rule must decide each pair jointly.
Counterexample mode
Making the later half of the order true
A tempting rule is to make every literal in the later half of the order true. This rule ignores pairing, and it fails. Take the formula over the variables . Its only edge is , so the components are the four singletons . The ordering is topological, because the only constraint is that precedes . Its later half is , and declaring both true is not an assignment at all.
The rule from the note instead compares the positions of and . When , these positions are distinct, so exactly one of the two is later.
Why later, not earlier. Suppose . If were true, then would also be true, which is impossible. So the path forces to be false. This path alone forces a value but does not make the formula unsatisfiable. A reverse path would make this pair contradictory; a different variable might also make the formula unsatisfiable.
If the two components are distinct, the path makes the component of precede that of in every topological order. If they coincide, the formula is unsatisfiable by the criterion. In the distinct-component case, the "later" rule therefore makes true, which agrees with the forcing.
The "earlier" rule disagrees. For alone, the single edge yields the unique order .
- The later rule sets true, which satisfies .
- The earlier rule makes true, so is false and the clause fails.
Worked example 3.6.10
(A chain of singleton components)
Let . Each clause contributes the following edges:
- gives and .
- gives and .
- gives , which is its own contrapositive.
These five edges form the single path
The graph has no cycle, so all six components are singletons, and no literal is paired with itself. Because the path is a chain through every vertex, the only topological order is , at positions through .
Compare each pair of positions:
- is at position and at position , so is false.
- is at position and at position , so is false.
- is at position and at position , so is false.
Check each clause under :
- is satisfied, because is true.
- is satisfied, because is true.
- is true.
Worked example 3.6.11
(Components with several literals)
Let over the variables . Its edges are
The components are , , and . As the complement lemma predicts, . The only edge between components is .
Choose the order . It is valid because precedes .
- comes after its partner, so .
- comes after , so .
Check each clause:
- is satisfied by .
- is satisfied by .
- is true.
Swapping the first two components gives another valid order, and it yields , , which is also satisfying. Different topological orders need not produce the same assignment. The theorem only claims that each one produces some satisfying assignment.
Exercises
Exercise 3.6.12
(Analyze : find its components and decide whether it is satisfiable.)
Core
Solution(4)
- 1
Read off the edges
The clause gives the edge , and gives the edge .
- 2
Find the components
These edges form a cycle, so there is a single component with .
- 3
Compare positions
The only topological order is the one-item list . Its partner occupies the same position, so the comparison rule cannot decide , and the criterion declares the formula unsatisfiable.
- 4
Check directly
violates , and violates .
Exercise 3.6.13
(Show that admits both and .)
Core
Solution(4)
- 1
List the edges and components
The edges are , , and . The components are and , with no edges between them, so both orderings are topological.
- 2
Read off the first order
For the order the negated component is later, so . Both clauses hold, by and respectively.
- 3
Read off the second order
For the order we get . Both clauses hold, by and respectively.
- 4
Exclude the mixed assignments
With and the first clause fails; with and the second fails. This matches the graph: and lie in one component, so they are forced to agree.
Membership in NL
Let 2-UNSAT be the language of well-formed unsatisfiable 2-CNF formulas; malformed strings are rejected. Its nondeterministic logspace machine first checks the encoding. It accepts immediately if an empty clause is present. Otherwise it guesses a variable , guesses a path from to , and subsequently guesses a path back. If there are literal vertices, each reachable pair has a simple path of at most edges. Store the current vertex, the chosen variable and an -bit step counter. Store a literal by its position in the explicit variable list and a sign bit, rather than copying an arbitrarily long binary label. To check a guessed edge, rescan the variable and clause lists for a clause that produces it. Thus both path searches use work bits, where is the input length. The two searches are sequential on the same computation branch: acceptance requires both to succeed for the same variable.
The criterion proves that this machine accepts exactly 2-UNSAT. By the theorem established in the reachability notes, the ordinary complement of 2-UNSAT is in NL. A preliminary deterministic logspace encoding check rejects malformed input, leaving precisely the language 2-SAT of well-formed satisfiable formulas. Therefore both languages lie in NL.
Common mistake
(Swapping accepting and rejecting states)
Complementing a nondeterministic machine by simply exchanging accepting and rejecting states does not prove closure under complement. On one input a rejecting branch can coexist with an accepting branch, so the swapped machine accepts that input as well. The proof uses instead.
Hardness from reachability
Theorem 3.6.14
(2-SAT and 2-UNSAT are NL-complete)
Under deterministic logarithmic-space many-one reductions, both 2-SAT and 2-UNSAT are NL-complete for the explicit encoding above.
For a directed graph with designated , introduce one variable per vertex. Output the unit clauses and , and for each edge output
The edge clauses force truth to propagate along every directed path. If is reachable from , the first unit clause forces true, contradicting the second. Conversely, if is not reachable, assign true exactly for vertices reachable from . The two units hold, and every edge clause holds: an edge from a reachable vertex ends at a reachable vertex. This is a proof of existence of an assignment, not a request that the reduction compute the reachable set.
The reduction streams one clause per edge using vertex counters and repeated scans of the explicit graph; it never stores the formula or a reachability set. It uses logarithmic workspace and polynomial output length. If , the two unit clauses already conflict, matching zero-length reachability. Thus STCON reduces to 2-UNSAT, proving NL-hardness of 2-UNSAT.
For 2-SAT, take any language . By , its complement is in NL and reduces to STCON. Compose that reduction with the graph-to-formula mapping above. The resulting well-formed formula is satisfiable exactly when the graph has no -to- path, hence exactly when the original input belongs to . Standard logspace-reduction composition gives a logspace reduction. Together with membership, both completeness claims follow.
Common mistake
(Satisfiable means unreachable)
The formula built from is satisfiable exactly when is not reachable from . It therefore reduces STCON to 2-UNSAT directly. Reading it as a reduction of STCON to 2-SAT is wrong: that needs the complement of STCON, which is where enters.
Worked example 3.6.15
(Encoding a reachability instance)
For vertices and edges , , with , the formula is
The first and edge clauses force , contradicting . If the second edge is deleted, and satisfy the remaining formula.
Exercises with solutions
Quick check
(Does have a satisfying assignment?)
Fix first.
Solution · Answer
No. The first two clauses force and respectively when is false; the third requires false. Equivalently, the implication graph has paths in both directions between and .
Quick check
(Give a formula having a path but still satisfiable.)
One clause is enough.
Solution · Answer
The unit clause has the edge and is satisfied by . There is no reverse path.
Quick check
(What assignment shows that the graph-to-formula construction is satisfiable when is unreachable?)
Use the vertices reachable from .
Solution · Answer
Make exactly the vertices reachable from true. No edge can go from this set to its complement, so every edge clause is satisfied; the two unit clauses also hold.
Quick check
(Why can both path guesses be stored in logarithmic space?)
What must be remembered at one moment?
Solution · Answer
Store only one current literal and one bounded counter at a time, and retain the selected variable while restarting the search in the reverse direction. The paths themselves need not be stored.
Quick check
(Does this proof give a deterministic logspace algorithm for 2-SAT?)
Which step is nondeterministic?
Solution · Answer
No. It uses nondeterministic reachability and . Such an algorithm would, by the hardness reduction, imply .