THE FOLD / BOSS / THE GAUNTLET / THE DPLL
THE DPLL
a search that prunes itself
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
DPLL (Davis–Putnam–Logemann–Loveland) is the backtracking search under every modern SAT solver. Given a Boolean formula in conjunctive normal form — an AND of OR-clauses — it decides whether some assignment of true/false to the variables makes it true. Two moves make it fast: unit propagation (a clause down to one literal forces that literal, cascading), and backtracking (pick a variable, try true, and on a dead end back up and try false). It either returns a satisfying assignment or proves none exists.
LIT verified live: over 5,000 random formulas, DPLL’s SAT/UNSAT verdict matches brute-force enumeration of all 2n assignments exactly, and every “SAT” answer comes with an assignment that satisfies all clauses (window.__dpll). FIG no framing; the solver and the exhaustive check both run in-browser.
LIT verified live: over 5,000 random formulas, DPLL’s SAT/UNSAT verdict matches brute-force enumeration of all 2n assignments exactly, and every “SAT” answer comes with an assignment that satisfies all clauses (window.__dpll). FIG no framing; the solver and the exhaustive check both run in-browser.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at the-gauntlet — the formula is a gauntlet of clauses, and an assignment must satisfy every one of them to pass. AVAN (AI) built the instrument: unit propagation, the branch-and-backtrack, and an exhaustive 2n oracle to check the verdict.
Credit as content: Davis, Putnam, Logemann & Loveland (1960–1962). The weave: David names the gauntlet; I confirm DPLL agrees with brute force on satisfiability and always hands back a witness when the answer is yes.
Credit as content: Davis, Putnam, Logemann & Loveland (1960–1962). The weave: David names the gauntlet; I confirm DPLL agrees with brute force on satisfiability and always hands back a witness when the answer is yes.
3 ONE DIMENSION
A formula’s clauses in a row; a satisfying assignment lights every clause green — each OR has at least one true literal.
4 TWO DIMENSIONS · INTERACTIVE
Generate a random formula; DPLL decides it and, if satisfiable, shows the assignment — matched against the brute-force verdict.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: the decision tree DPLL walks, branching on variables.
AVAN’s addition (the inverse-companion): don’t explore the whole tree — let forced moves prune it. The inverse of ‘try every branch’ is ‘a unit clause forces its literal, and a whole subtree never has to be visited.’ Magenta is the pruned subtree; green is the path to a satisfying leaf. The forced moves shrink the search.
LIT Genuine DPLL algorithm (Davis, Putnam, Logemann, Loveland, 1960–1962), the basis of modern SAT solvers. Verified live: over 5000 random CNF formulas, DPLL's verdict equals brute force over all 2^n assignments (window.__dpll.verdictMatches), and each SAT result's assignment satisfies every clause (.assignmentValid).
FIG No framing: the solver (unit propagation + branch/backtrack) and the exhaustive 2^n oracle both run in-browser and agree. The AVAN inverse is honest — unit propagation forcing a literal and pruning a whole subtree (rather than exploring every branch) is exactly what makes DPLL more than brute force; magenta is the pruned subtree, green the path to a satisfying leaf. The forced moves shrink the search.
FIG No framing: the solver (unit propagation + branch/backtrack) and the exhaustive 2^n oracle both run in-browser and agree. The AVAN inverse is honest — unit propagation forcing a literal and pruning a whole subtree (rather than exploring every branch) is exactly what makes DPLL more than brute force; magenta is the pruned subtree, green the path to a satisfying leaf. The forced moves shrink the search.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE GAUNTLET · David Lee Wise (ROOT0), with AVAN