THE FOLD / GLITCH / HEISENBUG / THE 2-SAT
THE 2-SAT
satisfiability in linear time — a contradiction is a cycle
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
2-SAT asks whether a set of constraints, each an OR of two boolean literals like (x ∨ ¬y), can all be satisfied at once. Full SAT is NP-complete, but the two-literal case is solvable in linear time.
The trick: each clause (a ∨ b) means ‘if not a then b’ and ‘if not b then a.’ Build these implications as a directed graph, find its strongly-connected components, and the formula is satisfiable iff no variable x and its negation ¬x land in the same component — if they are forced equal, contradiction. The assignment reads off from the components in reverse order.
LIT verified live: the SCC verdict matches brute force over all 2ⁿ assignments for 300 random formulas, and when satisfiable the returned assignment satisfies every clause (window.__twosat). FIG no framing; exact constraint solving.
The trick: each clause (a ∨ b) means ‘if not a then b’ and ‘if not b then a.’ Build these implications as a directed graph, find its strongly-connected components, and the formula is satisfiable iff no variable x and its negation ¬x land in the same component — if they are forced equal, contradiction. The assignment reads off from the components in reverse order.
LIT verified live: the SCC verdict matches brute force over all 2ⁿ assignments for 300 random formulas, and when satisfiable the returned assignment satisfies every clause (window.__twosat). FIG no framing; exact constraint solving.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at heisenbug — a contradiction that either lurks or doesn’t, invisible until you resolve it. 2-SAT decides exactly that: is a consistent assignment possible? AVAN (AI) built the instrument: the implication graph, the SCC condensation, the assignment reader, the brute-force check.
Credit as content: Melven Krom (1967); the linear-time SCC method of Bengt Aspvall, Michael Plass & Robert Tarjan (1979). The weave: David names the heisenbug; I turn clauses into implications, find the strongly-connected components, and read satisfiability off whether any literal is forced equal to its own negation.
Credit as content: Melven Krom (1967); the linear-time SCC method of Bengt Aspvall, Michael Plass & Robert Tarjan (1979). The weave: David names the heisenbug; I turn clauses into implications, find the strongly-connected components, and read satisfiability off whether any literal is forced equal to its own negation.
3 ONE DIMENSION
One clause (a ∨ b) becomes two implications: ¬a → b and ¬b → a. A whole formula becomes a directed graph, and satisfiability is a question about its cycles.
4 TWO DIMENSIONS · INTERACTIVE
Toggle clauses; the implication graph is built and its strongly-connected components found. The verdict (satisfiable or not) and a valid assignment are read off, and checked against brute force.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: the implication graph condensed into components — a valid assignment read off in reverse topological order.
AVAN’s addition (the inverse-companion): satisfiability is decided by a symmetry of the implication graph, not by search. The clause structure makes the graph skew-symmetric under the map x ↔ ¬x, and the formula fails exactly when this map collapses a variable and its negation into one component — because then every truth value implies its own opposite, a self-contradiction loop with no escape. The inverse of ‘try all 2ⁿ assignments’ is ‘check whether the forced-implication cycles ever equate a literal with its negation.’ Magenta is the fatal cycle binding x to ¬x; green is the component condensation whose reverse order names a solution. Contradiction is a cycle you can see, not a search you must run.
LIT Genuine 2-SAT via implication graph + SCC (Krom 1967; linear algorithm Aspvall, Plass & Tarjan 1979). Verified live: the SCC-based solver's satisfiability verdict matches brute force over all 2^n assignments for 300 random formulas, and when satisfiable the returned assignment satisfies every clause (window.__twosat.verdictMatchesBrute && .assignmentValid).
FIG No framing: the implication graph, the Kosaraju/Tarjan SCC, the assignment reader, and the brute-force check run in-browser and agree exactly. The AVAN inverse is honest — unsatisfiability is exactly a variable and its negation sharing an SCC (a self-implication cycle), decided without searching 2^n assignments; magenta marks that fatal cycle.
FIG No framing: the implication graph, the Kosaraju/Tarjan SCC, the assignment reader, and the brute-force check run in-browser and agree exactly. The AVAN inverse is honest — unsatisfiability is exactly a variable and its negation sharing an SCC (a self-implication cycle), decided without searching 2^n assignments; magenta marks that fatal cycle.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of HEISENBUG · David Lee Wise (ROOT0), with AVAN