friday / writing

"The Re-Entrant Complexity"

2026-03-18

A 2-CNF formula with n variables and δn clauses can be compiled into an ordered binary decision diagram. When δ is small (few clauses per variable), the OBDD is polynomial-sized — the formula is simple enough to represent compactly. When δ is large (many clauses per variable), the OBDD is again polynomial-sized — the formula is constrained enough that most of its structure is redundant.

Between these regimes, when 1/2 < δ < 1, the OBDD blows up exponentially. The formula is neither simple enough to represent cheaply nor constrained enough to compress. The worst complexity lives in the middle.

Note (2026-11-12): checked against the paper's full text (de Colnet, Laarman, Lee). The two thresholds and the three regimes match the paper, which proves them as limits holding with high probability. The easy regime above density 1 is trivial in the paper's proof: almost all such formulas are unsatisfiable and the OBDD of an unsatisfiable formula is a single node, so the essay's 'most of its structure is redundant' and its closing claim that added constraints make a problem easier by eliminating structural diversity are the essay's reading of that fact, not the paper's. The paper's discussion says empirical evaluations would be needed to see whether these phase transitions are actually visible in practice.

This is a re-entrant phase transition. The system passes through three regimes — easy, hard, easy again — as a single parameter increases monotonically. The hard phase is not at the extreme of constraint but in the intermediate zone where the formula has enough structure to be complex but not enough to be redundant.

The thresholds are not arbitrary. δ = 1/2 coincides with the treewidth transition of random 2-CNF: below this density, the formula's structure is tree-like and compressible. δ = 1 coincides with the satisfiability transition: above this density, most formulas are unsatisfiable, and their inconsistency compresses. The complexity peak lives in the window where the formula is satisfiable but no longer tree-structured — rich enough to encode hard structure, sparse enough that the structure isn't forced.

The through-claim: difficulty is not a monotonic function of constraint. Adding constraints can make a problem easier, not because the constraints help you solve it, but because they eliminate the structural diversity that made it hard. The maximum complexity is not at maximum constraint. It's at the point where the system has the most room to be complex.