Elimination, compiled representations and the input deadline

5 October 2026. Primary-proof review and its consequence for equal-support SAT.

The question was whether elimination-based counting or compiled representations could remove the common literal order from our native SAT construction. The review led to a positive result on equal supports: single-copy clauses in arbitrary literal order now have a native recognizer. The useful invariant is the number of distinct forbidden assignments, together with explicit survivors near exhaustion.

Three primary papers were studied through the proof chains relevant here, rather than through abstracts. They explain why a small representation alone does not settle a per-symbol recognition question, and where a different schedule can help.

What the proofs provide

Brault-Baron, Capelli and Mengel, Understanding model counting for beta-acyclic CNF-formulas, Sections 3–4, Theorems 10, 11, 25 and 26. At a nest point, incident scopes form an inclusion chain. Projecting exceptional tuples does not enlarge their number. Ratios of successive sums of products telescope, preserving the partition function up to the domain size; nonnegativity makes a zero denominator safe. The runtime proof uses dependency downsets and separator cancellation to express each nonzero updated weight as a normalized ratio of original conditional partition functions. The arithmetic-operation bound is $O(s(I)^2\|I\|)$; finding the order, manipulating supports and rational arithmetic remain charged offline work. Section 4 first merges identical scopes. For our equal-support case, that requires aggregating distinct forbidden assignments, precisely the association task still needed under permuted literals. General rational inputs also require their input-weight bit budget in the bit-size accounting; SAT’s zero/one weights avoid that extra parameter.

Capelli, Understanding the complexity of #SAT using knowledge compilation, Sections 3–4, Lemmas 2–6 and Theorems 8–12. A decreasing-path argument bounds the uneliminated variables of an ordered subhypergraph by one edge. Maximal surviving subproblems then have disjoint remaining variables, permitting decomposable conjunctions and decision gates. Theorem 8 constructs a decision-DNNF in polynomial time with linearly many gates, but potentially unbounded fan-in; gates are not constant-degree records. Its lower bound applies to structured DNNFs, through induced matchings and rectangle covers. It concerns representation size for complete assignment functions, not native recognition. The construction uses stored incidence information, elimination order and computed subproblem membership. None is a free serial-name operation.

Bova, Capelli, Mengel and Slivovsky, Knowledge Compilation Meets Communication Complexity, Section 3 and Section 5. Decomposability lets a certificate through a gate be split and recombined independently inside and outside its variable set. This gives a rectangle. Eliminating gates yields a cover, disjoint under determinism; choosing balanced gates gives the size connection. Structured circuits additionally provide covers across prescribed vtree cuts. These arguments depend on the circuit’s decomposable certificate structure. A native scaffold’s labeled unfolding is not thereby such a certificate or a communication protocol. The paper’s deep external lower-bound premises are not imported into a new scaffold claim here.

A direct specialization identifies the dynamic quantity

Let $P$ be the set of distinct full assignments excluded by equal-support clauses on $V$. The conjunction’s truth function is $1-\mathbf 1_P$. Averaging out $X\subseteq V$ gives, for an assignment $t$ on the remaining coordinates,

$$f_X(t)=1-\frac{|\{p\in P:p|_{V\setminus X}=t\}|}{2^{|X|}}.$$

This follows directly by summing the indicator over the $2^{|X|}$ extensions. Thus the relevant quantities count distinct forbidden assignments in fibers, not clause occurrences. Repeating a clause changes no fiber count. Under a fixed coordinate order, a new distinct assignment changes one fiber at each level.

Eliminating everything and keeping only the scalar is inadequate for later clauses. The formulas $x$ and $\neg x$ both have normalized count $1/2$, but appending $x$ preserves satisfiability only for the former. This is a failure of that retained state, not a language obstruction: unary native recognition is already established.

The successful construction retains the coverage structure and delays its update by one clause. Until few assignments remain, that delay cannot affect satisfiability. At exactly four surviving assignments, two additional record windows suffice to materialize their dictionaries and reconcile the pending clauses. Direct streamed comparison then replaces canonical-order insertion. The complete proof accounts for each window, including input ending during the transition.

Why circuit size is the wrong obstruction for this family

Nested-support formulas already admit a small static decision representation. Arrange variables by the successive differences of their nested supports. Each clause’s forbidden assignment is then a prefix. Build the binary trie of these prefixes, stopping at a forbidden terminal; absent branches accept. The resulting ordered decision graph has at most a constant plus the sum of clause widths in nodes, and bounded outdegree. Empty formulas and empty clauses are constant graphs.

If names are stored literally, charge each created node’s coordinate label to a corresponding literal occurrence; their total length is at most the input’s name length. This gives an $O(N)$ static representation in the ordinary encoding. It does not build the graph incrementally in that encoding. In particular, it does not supply the native input deadline.

Consequently the reviewed general beta-acyclic structured-circuit lower bound cannot be specialized into a size obstruction for our nested-support slice. Our positive result instead resolves a maintenance issue on equal supports. A proposed all-native lower bound would still need its own simulation with all addresses, identities, metadata, timing and control flow accounted for.

Priorities after the review

The new structural principle is bounded damage from pending input: each equal-support clause removes at most one possible assignment. This gives time to prepare an exact small survivor representation before the answer can become negative. It is more specific than polynomial-time elimination or small circuit size.

The next test is nested supports whose widths differ by at most a fixed constant. Against a largest support, each clause then removes a bounded number of assignments. However, the master support may grow late, and shorter records may omit extremely long names. A successful extension must handle both facts under the same ordinary encoding. Bounding width difference alone does not establish enough time for a master-name scan.

The unrestricted nested-support language and many independent local cores remain open. General weighted-elimination implementation, big-integer arithmetic and generic circuit compilation are not the next agenda. The precise target is a native representation transition whose remaining uncertainty and required name work are both bounded by the arriving records.

The imported algorithms and circuit bounds are established literature. The fiber identity and static prefix graph are elementary specializations. The additional written native result is the capped-hole marker invariant and the transition to four explicit survivors, reusing the program’s FIFO/dictionary/compiler proofs. Independent audits and finite semantic checks support this construction; no formal verification is claimed. Full primary texts and extraction files are not included in the public source.