Constructive obstruction and minimum-cost predictive completion

Constructive obstruction and minimum-cost predictive completion

Target descent and the coarsest sufficient extension provide the information criterion used below. This section adds an exact finite compiler, a minimum-cost realization procedure within a specified sensor menu, and an analytically solved nonlinear dynamical family. Its ETH consequence is conditional on the supplied counting theorem. The executable backend is a conventional bounded-cache DPLL counter, not an implementation or practical speed demonstration of that theorem. The abstract criterion and coarsest joint-image completion are already established in Rodgers’s target-relative completion papers[10, 11]. The algorithms below realize that criterion within finite circuit and menu representations. The finite synchronous application is not an extension of the Hilbert-space analytic hypotheses of projected-dynamics theory.

Exact circuit reduction and conditional complexity

An input model consists of Boolean source bits and a Boolean circuit with gates, each of fan-in at most two; unary and constant gates are included in. Its designated outputs are an admissibility bit , a present readout and a target. The source is . Source labels have no gauge redundancy in this finite model; an application with redundant coordinates must first specify its quotient or invariant target. Sensor outputs are additional nominated circuit wires and are included in the circuit size. Let be the number of distinct target wires.

Theorem 2.1 (Parsimonious collision compilation). There is a 3-CNF whose satisfying assignments are in bijection with ordered pairs satisfying

Searchable transcription

π(x) = π(x′),
R(x) ̸= R(x′).

It uses at most variables and clauses after duplicate output comparisons are removed. Reading the supplied output lists incurs their usual polynomial description cost. Every satisfying source pair has exactly one extension to the gate variables. The theorem also holds for the readout augmented by any selected sensor subset.

Proof. Take two copies of the circuit. For every gate, forbid each inconsistent input/output truth-table row. A binary gate contributes at most four clauses of width three, a unary gate at most two clauses of width two, and a constant a unit clause. Topological induction forces every gate variable uniquely once its source inputs are fixed. Add the two unit clauses) = 1 and two width-two clauses for equality of each distinct readout wire across copies. There are at most distinct such wires even

when the supplied output or sensor lists repeat them. For each distinct target wire form its two-copy XOR. A binary OR tree over those XORs is constrained to one; this adds at most 21 gates and their unique values. If there is no target coordinate, insert an empty clause instead. Thus every source pair either has no extension or exactly one, and it has one precisely under the displayed condition. All comparison gates and normalization constraints are counted.

Corollary 2.2 (Conditional constructive descent test). Assume the fixed-density part of the supplied OpenAI preprint’s Theorem 1.1[7]. The ordered collision count, a collision witness when one exists, and hence exact target descent can be computed in

Searchable transcription

poly(description length) 2O(V/√log V )

bit operations and polynomial space, with finite exceptional sizes handled directly. In particular , together with a polynomial-length supplied circuit/output/menu description, gives a subexponential-in-source-bits test even for globally dependent targets. For larger circuits the bound is in the compiled size ; polynomial circuit size alone does not imply subexponential time in

Proof. The compiled width is three and clause density is bounded by an absolute constant. Apply Theorem 1.1 and recover source bits by variable-by-variable self-reduction, using only polynomially many counting queries. A zero count is exactly fibre constancy by Rodgers’s criterion. Gate extension uniqueness ensures there is no multiplicity correction. An empty source gives count zero vacuously; the implementation reports that case explicitly.

For fixed-locality admissibility and readout predicates and a binary fixed-local target, a direct truth-table construction instead uses the two source copies alone and constant-width clauses, as in Appendix C.2. A multi-coordinate target can be tested for descent coordinate by coordinate; summing those collision counts would double-count pairs that disagree in several coordinates and is not the union count. The compiler above is broader: global parity, nonlinear global feedback and circuits reusing intermediate values are permitted. Its gates for every menu item are compiled even if that item is not selected; unused-gate cone elimination is not assumed in the complexity or executable counts. The same one-copy gate encoding counts compatible source/target values. For a specified finite prior weight0, the appropriate conditional answer is

Searchable transcription

∑︁
x:C(x)=1, π(x)=t, R(x)=a w(x)
Pr(R = a | π = t, C = 1) =
∑︁
x:C(x)=1, π(x)=t w(x)
.

A zero denominator is reported as impossible or zero mass, never normalized. Uniform compatible-source counting is the special nominated prior1, not a consequence of the readout and not a Born-selection argument. The implementation’s arbitrary rational prior table uses exact enumeration; it is not labelled a fast weighted ETH backend.

Counterexample-guided minimum-cost realization

Searchable transcription

Let M sensor items gj have nonnegative exact rational costs cj. An item can return several bits. An
independently specified decidable family F ⊆2[M] declares jointly feasible selections; it may encode
incompatibility, resource caps or prerequisites. It need not be upward closed. The realized readout for
selection A is
eA(x) = (π(x), (gj(x))j∈A),
c(A) =
∑︂
j∈A
cj.

The optimizer can also be generalized to another exactly specified finite cost function; the supplied implementation uses additive costs.

For a current collision () define. Every sufficient selection must hit this set. Maintain such sets, minimize) over that hit all of them, and call the exact collision oracle on. If it returns a pair, append that pair’s set and reoptimize the entire selection. If it certifies no pair, return. If a returned set is empty, the whole menu is insufficient; if the constrained optimization is infeasible, no feasible sufficient selection exists.

Theorem 2.3 (Exact minimum-cost completion synthesis). With exact optimization and separation, this algorithm terminates and returns either a globally minimum-cost sufficient feasible selection or a sound impossibility result within the declared menu/family. No tested candidate selection repeats. There are at most separation calls, with at most one subsequent infeasible optimization.

Proof. Every true sufficient selection separates every returned target-disagreeing pair, so it satisfies every accumulated cut. The current restricted optimization value is therefore a lower bound on the true optimum. If the chosen candidate has no collision, it is a sufficient feasible selection of exactly that cost, giving a matching upper bound. If it has a collision, none of its selected sensors belongs to the new), so the new cut excludes this candidate permanently. Finiteness proves termination. An empty distinguishing set forbids every subset; otherwise infeasibility of the accumulated necessary cuts within forbids every feasible sufficient selection. Each cut’s witness, selected set and exact cost are retained in the trace.

This is an application of established counterexample-guided synthesis and implicit hitting-set optimization, not their invention. Close antecedents include Solar-Lezama’s Program Synthesis by Sketching (2008), Chandrasekaran–Karp–Moreno-Centeno–Vempala, Algorithms for Implicit Hitting Set Problems (SODA 2011, DOI 10.1137/1.9781611973082.48), and Moreno-Centeno–Karp, The Implicit Hitting Set Approach to Solve Combinatorial Optimization Problems with an Application to Multigenome Alignment (2013, DOI 10.1287/opre.1120.1139)[2, 5, 16]. The source-specific contribution here is the typed collision compiler, admitted-cost interface, exact verification and application to a proved predictive-completion frontier. The complexity is the sum of all optimizer and separation calls. An ETH-fast separation oracle does not make the whole synthesis subexponential: the finite selection family itself may be exponential. The prototype re-enumerates subsets exactly, with no performance-optimality claim. A feasible returned selection alone is not a certificate if the final oracle is incomplete. The supplied iteration cap returns incomplete explicitly. More generally, a certified lower bound on a restricted optimum and a fully validated sufficient selection of cost certifyOPT. If each approximate optimizer guarantees cost at most times the current restricted optimum plus, with1 and0, final exact separation givesOPT. Unvalidated heuristic proposals or absence of a discovered counterexample supply no such guarantee. Reoptimization matters even on a two-bit source. Let the target be, with no initial readout. Offer three singleton-indicator sensors for states 01 11 at unit cost, and raw-bit sensors at cost 65 each. Greedily adding a cheapest sensor for each returned collision buys all three indicators, cost 3. Reoptimization finds one raw-bit sensor and the missing singleton, cost 115. No cheaper selection can cover all three target-disagreeing state pairs: two unit indicators miss one and a lone raw bit misses one. The exact prototype and an independent subset check both reproduce this gap.

A sharp nonlinear predictive-completion resource frontier

This family turns the compiler into a constructive autonomous-dynamics application to target-relative descent[10] and a finite synchronous counterpart of exact projected-dynamics closure[12]. For

use 2 classical bits and one fixed clock tick, with source update

Searchable transcription

2b−1
⨁︂
F0(x) = x0 ∧
i=0
xi,
Fi(x) = xi
(i > 0),
π(x) = x0.

All source states are admissible. The target is the next observed bit, which depends globally and nonlinearly on the source. The permitted readers are the individual hidden-bit ports 0, and disjoint pair-parity ports. A direct global target reader is not in the menu. The source is a declared synchronous classical logic model. The ports read the same classical register nondestructively; joint measurement is therefore admitted. The task predicts the future from records acquired before the first update; waiting to observe the target after that update does not satisfy the prediction task. Only the stated present-time ports are admitted. No laboratory prediction-deadline or timing advantage is certified by this discrete model. A pair-parity port is a separately admitted two-bit reader with a specified cost, not a free computational substitute for physically inaccessible bits. Clock, fixed logic and archival choices are external specified resources. No energy, continuous-time or quantum efficiency conclusion follows from the cost units.

Theorem 2.4 (Exact predictive versus full-source port cost). Give raw port positive cost and pair port positive cost, with no other joint constraints. The minimum cost of a readout determining every future observed bit is

Searchable transcription

b−1
∑︂
Cpred = min{u1, v0} +
j=1
min{u2j + u2j+1, vj}.

The minimum cost for full source reconstruction is

Searchable transcription

b−1
∑︂
Cfull = min{u1, v0} +
j=1
min{u2j + u2j+1, u2j + vj, u2j+1 + vj}.

Under unit port costs, and. The selected predictive ports can be chosen so their augmented readout itself has an autonomous update, rather than merely predicting one step.

Searchable transcription

Proof. Restrict to the admitted subfamily x0 = 1. Then the target is global parity. Holding every
other block fixed shows that the selected sensors in each block must determine its pair parity. In
block zero, known x0 makes either x1 or p0 sufficient and at least one necessary. In another block, a
pair-parity port suffices; without it, both raw bits are necessary because changing an unmeasured bit
flips the target while preserving every measured output. The blocks have disjoint sensor scopes, so
their independently necessary minima add and the displayed selection attains the sum. For full source
reconstruction, each other block has four independent states and any two of its three possible binary
ports recover both bits; fewer than two cannot do so. This proves its sum.
Write q = ⨁︁
i>0 xi. If x0 = 0 it remains zero. If x0 = 1, the next bit is 1 ⊕q: it remains one when
q = 0, otherwise becomes zero and stays zero. Hence all future readouts equal R after the first step, so
one-step sufficiency is all-future sufficiency. Selected raw ports are fixed under F. Pair ports for j > 0
are also fixed; if p0 is selected, it updates as p′
0 = p0 ⊕x0 ⊕R. Thus the cost-attaining augmented
readout closes autonomously.

The ideal canonical predictive completion has only three states,

Searchable transcription

(π, R) ∈{(0, 0), (1, 0), (1, 1)},

with autonomous transitions 0011. Under unit costs the displayed minimum-cost port signature contains 2 distinct values, and its postprocessing yields this three-state quotient. If

raw port records are retained, that larger archive is not discarded from the resource account. Abstract minimal distinctions and minimum physical-menu access cost are different quantities. Under unit costs the gap approaches a factor of two, but that is a declared port-cost result, not a universal hardware advantage. If raw ports cost and each pair port costs 2, the predictive optimum , the same as the raw strategy. The exact weighted formula therefore exposes the premise on which a gain depends. For the source family, the initial ordered collision count is 2: only = 1 contributes, with 2 sources of each target value, counted in both orders. For 5 the compiler and exact synthesizer reproduce costs 1 5 against raw/full-source costs 1 9, and yield autonomous completion signatures on every source state. Exhaustive whole-subset checks establish independent optima for the smaller sizes; twelve unequal rational-cost tests verify both weighted formulas. A uniform admitted-source prior gives Pr2; separately nominated weights three on = 1 and one on = 0 give 34. Neither prior is selected by the readout or by ETH.

Implementation, verification and scope

The implementation consists of completion.py and verify_finite.py. It uses exact inte-gers/Fractions and a conventional DPLL counter with a cache bounded to 4096 states. It includes truth-table circuit compilation, a two-copy obstruction oracle, compatible target counts, exact finite-prior reference calculations, menu constraints, reoptimized synthesis and explicit incomplete/empty-source statuses. Inputs with malformed bits, sensor indices, costs or negative prior weights are rejected. Nonuniform prior tables are globally validated, including entries outside the queried fibre. The tests compare randomized CNF counts, unique gate extensions, random nonlinear constrained models, every sensor subset, compatible target counts and finite optima against direct source enu-meration. They also cover empty sources, impossible readouts, empty targets, infeasible hardware constraints and early stopping. The independent audit uses a distinct source-enumeration implemen-tation. Numerical runtime measurements describe this prototype only; no ETH-backend speedup is claimed. This work adds a constructive finite synthesis interface and a sharp menu-constrained dynamical example to the supplied baseline. Continuous CP feasibility is not replaced by an unrestricted Boolean decision problem. Source identification, source accessibility and source counting remain distinct.