THE FOLD / BOSS / THE GATEKEEPER / THE 2-SAT
THE 2-SAT
satisfy two-literal clauses in linear time
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
2-SAT asks whether a set of clauses, each an OR of two literals, can all be satisfied — and unlike general SAT (NP-complete), it is solvable in linear time. The trick: each clause (a ∨ b) becomes two implications, ¬a → b and ¬b → a, forming a graph. The formula is satisfiable iff no variable and its negation land in the same strongly connected component; a valid assignment is then read straight off the component order.
LIT verified live: over 300 random instances, the SCC-based verdict matches a brute-force check of all 2n assignments, and the extracted assignment satisfies every clause (window.__twosat). FIG no framing; exact.
LIT verified live: over 300 random instances, the SCC-based verdict matches a brute-force check of all 2n assignments, and the extracted assignment satisfies every clause (window.__twosat). FIG no framing; exact.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at the-gatekeeper — the check that decides, quickly, whether a web of two-way constraints can all be met. 2-SAT is that decision. AVAN (AI) built the instrument: the implication graph, the Tarjan SCC condensation, the same-component test, the component-order assignment, and the brute cross-check.
Credit as content: Aspvall, Plass & Tarjan (linear-time 2-SAT, 1979). The weave: David names the-gatekeeper; I turn each clause into two implications, condense the graph into components, and confirm satisfiability exactly matches brute force with a valid assignment.
Credit as content: Aspvall, Plass & Tarjan (linear-time 2-SAT, 1979). The weave: David names the-gatekeeper; I turn each clause into two implications, condense the graph into components, and confirm satisfiability exactly matches brute force with a valid assignment.
3 ONE DIMENSION
(a ∨ b) means: if a is false then b must be true, and if b is false then a must be true. Follow every such implication; if a variable can force both itself and its negation, the formula is unsatisfiable.
4 TWO DIMENSIONS · INTERACTIVE
A set of 2-clauses; the implication graph is condensed and checked, and a satisfying assignment is shown when one exists.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: satisfiability decided by component structure.
AVAN’s addition (the inverse-companion): decide a whole web of two-literal constraints in linear time by turning clauses into implications and asking whether any variable and its negation share a strongly connected component. The inverse of ‘try all 2n assignments’ is ‘chase implications, condense to components — satisfiability falls out.’ Magenta is the exponential assignment search avoided; green is the linear implication graph. Constraints solved by reachability.
LIT Genuine linear-time 2-SAT (Aspvall, Plass & Tarjan 1979). Verified live: over 300 random instances, building the implication graph and condensing it with Tarjan SCC gives a satisfiability verdict identical to a brute-force check of all 2^n assignments, and the extracted assignment (by component order) satisfies every clause (window.__twosat.matchesBrute).
FIG No framing: the implication graph, the Tarjan SCC condensation, the same-component test, the component-order assignment, and the brute cross-check run in-browser and agree exactly. The AVAN inverse is honest — turning each clause into two implications and asking whether any variable and its negation share an SCC decides satisfiability in linear time; magenta is the 2^n assignment search avoided, green the implication graph. Constraints solved by reachability.
FIG No framing: the implication graph, the Tarjan SCC condensation, the same-component test, the component-order assignment, and the brute cross-check run in-browser and agree exactly. The AVAN inverse is honest — turning each clause into two implications and asking whether any variable and its negation share an SCC decides satisfiability in linear time; magenta is the 2^n assignment search avoided, green the implication graph. Constraints solved by reachability.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE GATEKEEPER · David Lee Wise (ROOT0), with AVAN