SAT with a first-clause base and finitely many extra variables

5 October 2026. Written native construction; the first clause’s support is retained in every later clause.

The survivor method extends beyond equal supports, even to supports that are not nested. Fix a constant $k$. Let the first clause use the variable set $S$. Require every later clause to contain every variable in $S$, and permit at most $k$ distinct additional variables across the entire input. The additional names and their first occurrences are not supplied in advance. Each clause may contain any subset of them, in any literal order.

Theorem. For every fixed $k\ge0$, satisfiability with these checked structural conditions has a deterministic forward native scaffolding-automaton recognizer under the ordinary single-copy encoding. Width and all name lengths are unbounded. The reversed language therefore has a PEG.

This includes two nested supports differing by one variable when a clause on the smaller support occurs first. It does not settle arbitrary ordering of those two supports: discovering the smaller support after larger clauses remains open. The first-clause condition is part of the language, checked by the recognizer; it is not a supplied decomposition or a claim of order independence.

Encoding and resources

Use C(+u,-v,...);, with nonempty binary-word names, significant leading zeros, distinct names within each clause, repeated clauses allowed, and no whitespace or extra end marker. Repeated names, malformed records and incomplete inputs reject. Empty input accepts. An empty first clause makes the conjunction unsatisfiable. No structure certificate, replay, padding, advice, externally prepared handles or EOF computation is present.

The native machine has fixed finite labels, degree and observation radius, fixed initialization at the unlabelled base, one new node per actual input symbol and final-control acceptance. It observes labelled pointer paths, not pointer identity or numerical addresses. The constants may depend on $k$, but not on support width, names or input length. The construction uses the strict FIFO, serial finite-payload dictionary and capped-hole coverage primitives proved in the equal-support construction, with its reviewed fixed-batch native compilation contract.

Let $b=|S|$ and $H=\sum_{u\in S}|u|$. Save the first-clause encounter order as a master FIFO containing $T=H+b$ tokens, one separator after each name. Every valid nonempty-base record contains at least

$$L_S=H+2b+3>T$$

actual symbols. A record containing extra names $E$ has exactly

$$L=L_S+\sum_{v\in E}(|v|+2).$$

Thus every complete master scan fits inside every later valid record, even when extra names have arbitrarily different lengths. If the actual input has length $N$, all preparation, scans, abandoned builders, trial cursor operations and immutable versions use $O_k(N)$ logical storage. The compiled native machine has $N+1$ physical nodes; literal pointer serialization takes $O_k(N\log(N+2))$ bits. The machine is deterministic.

Discovering and checking the structure

During the first clause build the frozen base dictionary, a master-name FIFO and a width FIFO with one token per base name. Reject duplicate names. During every subsequent record, run base membership lookup and current-record Seen lookup as each name’s bits arrive. The Seen dictionary rejects every repeated name, whether base or extra. Consume one width token exactly when a base name ends; reject underflow and require the width cursor empty at clause close. All base names are therefore present exactly once.

Maintain a second dictionary mapping additional names to indices in $\{1,\ldots,k\}$. Query it concurrently with base membership. If a name is outside the base and is not yet in the extra dictionary, assign the next unused finite index at its delimiter and commit its dictionary entry. Its path capsule has already been prepared while the bits arrived, so this is the same delimiter payload publication used by the existing dictionary. A speculative capsule for a base name may be discarded. Reject a genuinely new extra name once all $k$ indices are used. All dictionary values and the allocation counter are finite because $k$ is fixed.

This validates global distinct-extra count without a terminal scan. Record-local distinctness remains separate. Until structural validity is established, computation is speculative: a bad record cannot be accepted and does not need to supply a complete background work window. Work per symbol remains bounded even on invalid strings.

Fixed branches before the extra variables are known

Create $2^k$ branches from the outset, indexed by assignments $\alpha\in\{0,1\}^k$. When an extra name receives index $j$, branch $\alpha$ interprets its value as $\alpha_j$. Before index $j$ is used, branches differing only at that index have identical semantics. This creates no need to split or reconstruct an old branch when a name is discovered.

For a completed clause $C$, let $p_C\in\{0,1\}^S$ be the assignment falsifying its base literals. Let $M_C$ be the finite set of branches that falsify every extra literal in $C$. A positive literal requires bit zero; a negative literal requires bit one. Missing extra variables impose no condition. Build $M_C$ as a finite mask while the actual extra names arrive.

After fixing branch $\alpha$, clause $C$ has precisely this effect on base assignments:

$$U_\alpha\longmapsto \begin{cases} U_\alpha\setminus\{p_C\},&\alpha\in M_C,\\ U_\alpha,&\alpha\notin M_C. \end{cases}$$

Each branch loses at most one point per actual record. The whole formula is satisfiable exactly when at least one branch has a surviving base assignment. Unused indices only duplicate witnesses and do not alter this existential test. This equivalence follows by extending any assignment to the actually named extras arbitrarily over unused indices, and restricting a surviving branch assignment back to actual variables.

Store a base sign dictionary and $M_C$ for each pending clause. Dictionary construction can speculatively prepare paths before base membership becomes known, publishing only base entries at the delimiter. The extra mask does not need to be known until the whole record ends: delayed insertion uses completed records, and direct comparison applies the mask at record end.

The survivor schedule in each branch

For $b\ge3$, each branch starts with $2^b$ base assignments. Use the weighted-marker coverage structure of the equal-support proof, with hole count capped at five. During actual record $i+1$, branch $\alpha$ processes completed record $i$: insert $p_i$ if $\alpha\in M_i$, otherwise leave the root unchanged. A disabled clause takes no semantic action; it does not stop the actual-record clock.

There are finitely many parallel workers, all scanning the same $T$ master tokens. They may share stored sign dictionaries, but no sharing is needed for the cost bound. Each actual symbol performs a fixed number depending on $k$ of primitive calls. Long extra names increase available time; they are never traversed by a base scan.

If a branch’s processed root has more than four holes, its one pending record cannot exhaust them, so that branch certifies SAT at the current complete boundary. If a branch first reaches at most four holes after processing record $j$, it has exactly four: an enabled new point removes one, and all other updates remove zero. Freeze that branch’s root and use the following schedule, independently of the other branches.

The four-hole enumeration and two pending comparisons each use complete base scans, exactly as in the equal-support proof. The stored finite masks decide which matching candidates to remove. During live comparison, only base names affect the four equality flags. Extra literals affect $M_C$ instead; this distinction is decided at the name delimiter after concurrent base membership lookup. Querying a candidate dictionary speculatively on an extra name is harmless: its unsuccessful result is ignored.

A branch can be in a different phase from every other branch. At each valid complete record boundary, take the OR of their finite acceptance bits: the early phases have proved nonempty survivors, while the direct phase has an exact mask. This is a fixed finite operation for fixed $k$. The proof never assumes that another record will arrive.

For $b\le2$, build the four possible base candidate dictionaries during the first clause, retain exactly $2^b$ candidates, and remove its falsifying assignment in every branch. Thereafter direct comparison with the finite extra masks suffices. For $b=0$ the first empty clause rejects satisfiability permanently, though syntax and structure may continue to be checked. Empty input is handled separately.

Correctness and native accounting

Inductively, each processed branch root is the exact complement of its enabled forbidden base points. Its missing-count cap and hole enumeration inherit the weighted-marker invariant, including correct blank subtree heights. Before direct mode, pending actual records delete at most one point each in that branch, establishing the boundary guarantees in the table. At catch-up, two saved clauses and one live clause are incorporated exactly. Direct comparison then maintains the exact remaining candidate set. The branch equivalence above proves conjunction satisfiability; the independent structural checks prove membership in the stated language.

Every branch uses a fixed root family: one coverage worker, up to two pending records, four candidate dictionaries/builders and fixed comparison flags. Multiplying by $2^k$ still gives a fixed family. All serial dictionary operations, marker peeks and FIFO actions have bounded worst-case observations and allocations. Initialization consists only of fixed empty structures and branch control; the unbounded master is built from the actual first clause. The simultaneous-record compiler therefore gives one native automaton for all lengths for each fixed $k$. No numerical optimization of its degree or radius is claimed.

Why late removal of a base variable remains different

Suppose the first clause contains $S\cup\{z\}$ and the first smaller clause contains only $S$. Write $|z|=q$, $|S|=b$ and $H=\sum_{u\in S}|u|$. The old flattened master has $H+q+b+1$ tokens, whereas the shorter record has only $H+2b+3$ symbols. Their ratio is unbounded as $q$ grows with $S$ fixed. For any fixed scan rate $c$, choosing

$$q>c(H+2b+3)-H-b-1$$

prevents a fresh full old-master scan from completing during that shorter record. This is a failure of that scan schedule, not a lower bound against all native representations. Extra earlier time, precomputed skipping information, different coordinates or direct survivor dictionaries could change the situation.

A stopped-prefix witness makes the failure concrete. Put $S=\{0,1\}$ and let $z$ be the name consisting of $M\ge2$ zeros, first in the saved master order. Give four distinct clauses on $S\cup\{z\}$, then all four signed clauses on $S$. Each long record has $M+11$ symbols and each short record has nine, so actual total length is $N=4M+80$. At the fourth long-record boundary the unchanged one-record-lag procedure has processed three forbidden points, leaving five holes, and has its fourth point pending. If it begins that pending master scan at the fifth-record boundary and reads at most $c$ tokens per actual symbol, choose $M>36c$. It cannot finish even the first name during the four short records. Yet those four clauses already forbid every assignment on $S$. Continuing to interpret cap five as safe would accept an unsatisfiable input. This specifically refutes retaining the old scan schedule and its one-pending-record acceptance argument after arbitrary support decreases; it does not rule out a proactive, skip-aware or different representation.

Once full survivor dictionaries are already ready, a shorter clause can be compared against them by its actual names and can remove two full assignments. The unresolved case is a support decrease during the lag or enumeration phase. Increasing the survivor threshold alone does not bound the missing name mass or supply enough time for the old-master traversal. Enumerating on a newly observed shorter master would require connecting that order to the old coverage coordinates; that translation has not been constructed.

An independent audit suggested grouping master names into word capsules, so a known omitted name could be skipped without rereading its bits. That is a useful next mechanism only if the omitted coordinate can be identified and the coverage path traversed with the same bounded observations. Neither an identity test nor a free dictionary-difference operation is available. The present theorem avoids this gap by retaining the original base in every record; it does not silently repair the unrestricted ordering case.

Status and next test

This is a written native extension of the prior survivor construction, independently reviewed as an outline and a full draft. Conditioning on finitely many Boolean variables is classical; the additional implementation point is assigning their finite slots on first occurrence while preserving all branch histories, masks and per-symbol work windows. No new imported literature theorem is required. Finite semantic testing checks branch gating and stopped-prefix scheduling, not native primitive costs or the whole character parser. No formal verification is claimed.

Next resolve late support decrease for two supports differing by one variable. A useful decisive test is whether an unsupplied omitted coordinate can be located and skipped in the saved coverage order using only the incoming shorter clause’s symbols, without an unbounded scan of its missing name. Preserve the already completed survivor phase as the easy case, and concentrate on conversion from the earlier coverage representation.

Finite experiment: scripts/verify_base_extra_survivors.py passed 1,000 streams, 61,600 stopped prefixes and 231,000 branch boundaries, including 2,250 threshold transitions. Disabled updates, duplicate assignments, gradual extra-slot discovery and final exhaustive base contradictions were included. Check output.