Research · Papers · Adders, counters and the heap law · MF-122
Exact complexity of the canonical heap-prefix class
Complexity equals T(k,n) for the canonical heap-prefix class; transfer counterexample shows this does not prove unrestricted MC(A_{k,n})=T(k,n)
Published 2026-09-04
For everyone
Plain summary
In digital circuits, multiplicative complexity counts the minimum number of AND gates needed to compute a function when XOR gates are free. Circuit designers often structure complex multi-step computations into orderly building blocks. Here, we analyze the canonical heap-prefix class, where the circuit begins with its internal carry state arranged in a standardized initial form.
Under this restriction, the exact multiplicative complexity equals the target value T(k,n). Across all 46 tested parameter settings, the measured algebraic ranks match the theoretical baseline. This result holds only when starting from this specific canonical carry structure. A separate test on circuits with fixed hidden internal space found a counterexample showing that the bound does not transfer to unrestricted circuits, so the general complexity of unconstrained circuits remains open.
Result
Under the GF(2) XOR-free multiplicative complexity model, the multiplicative complexity of the canonical heap-prefix class equals T(k,n). Across all 46 audited parameter cells satisfying kn ≤ 20, both full and leading carry-top quotient ranks equal c_n.
The exact complexity holds strictly under the structural restriction defining the canonical heap-prefix class: the initial carry state is closed and canonical, while subsequent factor selections remain unrestricted. Due to an explicit transfer counterexample in fixed-hidden-space experiments, this result does not imply the unrestricted circuit complexity equality MC(A_{k,n}) = T(k,n).
Setting and definitions
The cost model is multiplicative complexity over GF(2) in XOR-augmented graphs (XAGs), where XOR and NOT gates are free and non-affine operations (AND gates) incur unit cost.
- A_{k,n}: Target family of Boolean multi-output functions parameterized by integers k and n.
- T(k,n): Predicted multiplicative complexity bound function for parameters k and n.
- Canonical heap-prefix class: Subclass of circuit implementations of A_{k,n} constrained to begin with a canonical, closed carry state, with subsequent multiplicative factors unrestricted.
- c_n: Target dimension for the carry quotient rank.
- Carry-top quotient ranks: Dimensions of the full and leading quotient spaces associated with the carry-propagation state at the top of the heap prefix.
Method
The theorem was established by formal proof and exhaustive computational verification across 46 parameter instances satisfying kn ≤ 20. Evidence tier: P + FC for the class theorem, FC + FR for the transfer counterexample.
The analysis computed quotient spans, affine sections, and state exposure properties:
- Full and leading carry-top quotient ranks were evaluated and confirmed to equal c_n across the parameter space, recorded in carry-top-quotients.json and quotient-spans.json.
- Structural properties of the canonical heap prefix were validated via affine section analysis recorded in heap-affine-sections.json and compared against bank structures in bank-span-compare.json.
- State exposure conditions were verified in state-exposure-checks.json.
- Fixed-hidden-space experiments produced a transfer counterexample, demonstrating that universal reduction from unrestricted circuits to the canonical heap-prefix class fails.
Reports: zkgolf-decomp/reports/EXP-FORK-CN.md, zkgolf-decomp/reports/SB-HEAP.md, zkgolf-decomp/reports/FCNS-C-POTENTIAL.md, and zkgolf-decomp/reports/STATE-OF-PROGRAM-V2.md.
Discussion
The theorem determines the exact multiplicative complexity of A_{k,n} within the canonical heap-prefix class.
Scope and limitations:
- Restriction to canonical heap prefixes: The bound T(k,n) is established only for circuits initialized with a closed, canonical carry state.
- Non-transferability: Fixed-hidden-space investigations yielded an explicit transfer counterexample. Structural constraints from the canonical heap prefix do not carry over to unrestricted XAGs computing A_{k,n}.
- Unrestricted complexity: The general equality MC(A_{k,n}) = T(k,n) remains unproven.
- Prior art: The register records no prior-art position.
For everyone — the takeaway
What this means
This result gives the exact number of AND gates needed to compute this family of functions, provided the circuit starts with an organized carry state. For these structured designs, the cost matches the theoretical target T(k,n) exactly.
Because other circuit layouts can bypass this initial carry structure, the formula does not apply to all possible implementations. The minimum complexity for arbitrary, unconstrained designs remains an open problem.
Register references
ID: MF-122
Reports:
- zkgolf-decomp/reports/EXP-FORK-CN.md
- zkgolf-decomp/reports/SB-HEAP.md
- zkgolf-decomp/reports/FCNS-C-POTENTIAL.md
- zkgolf-decomp/reports/STATE-OF-PROGRAM-V2.md
Receipt artifacts:
- zkgolf-decomp/exp-fork-scratch/carry-top-quotients.json (SHA-256 a6f19c75ca91c1c1ce36e4682ad0612a491f54bbed16e79befdfebd37b0534cf)
- zkgolf-decomp/exp-fork-scratch/heap-affine-sections.json (SHA-256 592b4a32d9888b2c463acdbe9bacb24c7886ceba31afe19a283e27957f903f12)
- zkgolf-decomp/exp-fork-scratch/state-exposure-checks.json (SHA-256 6455b2eb7f7514a2e70d49ec969498a65b57de5f8871789277bbca6862f4c48d)
- zkgolf-decomp/sb-heap-scratch/quotient-spans.json (SHA-256 fd0ca89bc2462df6ff9bb385ea6d5e421f7082eb6ecd28dd91e8962ef0dba635)
- zkgolf-decomp/sb-heap-scratch/bank-span-compare.json (SHA-256 3f4acab59326cd650539e17b848461429785a55c1d036ba28a2f90d3024a4679)
Prior art:
- The register records no prior-art position.
Every artifact named above is bundled in, or hashed by, this paper's evidence pack below.
Evidence pack
Everything needed to check this entry against its receipts: the register text, a manifest with a SHA-256 hash for every named receipt, and 4 of 9 receipt files bundled (39 KB). Anything not bundled is still hashed in the manifest and lives in the compute-box working trees.
Changelog
Last reviewed 2026-09-04
- 2026-09-04Published on this site.