# Exact selection and reconciliation witness assurance

Edition: 9 October 2026 Australia/Brisbane. Decision: **Prototype a bounded identity/count/witness assurance module; defer direct faster or low-space source backends.** Prices, workflow benefit and profitability remain unvalidated.

## Research finding

Family 138 contains two separate randomized positive-integer subset-sum decision results. The faster paper claims worst-case O(2^(0.49n)) word time in every fixed polynomial-bit regime, with two-sided error at most one third per fixed input. It answers YES/NO; it does not directly deliver an original-item witness or an exact count. The low-space companion claims polynomial-times-2^(n/2) word time with O(2^(n/5)) writable words, and one-sided error: no false YES, but a YES instance may return NO. Its sharper displayed space bound retains a polynomial factor times 2^(.199n).

The source reading now exposes their practical branches. For maximum input bit length b=64, the faster known guard b^100000 <= 2^n first passes at n=600,000; the low-space known guard n+b+2 <= 2^floor(n/10^9) first passes at n=36,000,000,000. Additional fixed cutoffs n_* and n0 have not been numerically selected in this review. Below the relevant cutoff or failed guard, the faster program falls back to exact meet-in-the-middle, and the low-space program enumerates all indexed subsets with O(n) writable words. The known guard being true does not establish readiness of either main branch.

These are source-text and exact parameter calculations, not independent proof acceptance or execution. No family formal-scope document is listed. The time and space savings cannot be combined into a single 0.49-time/0.2-space backend without another result. [Pinned fast implementation](https://github.com/openai/math/blob/fd4aeeb2ee4fc729c18d98444fed42fd0529eeeb/preprints/Subset-Sum-in-Time-2-power-0-49n-October-4-2026/build/sections/implementation.tex), [low-space implementation](https://github.com/openai/math/blob/fd4aeeb2ee4fc729c18d98444fed42fd0529eeeb/preprints/A-Low-Space-Algorithm-for-Worst-Case-Subset-Sum-September-26-2026/build/implementation.tex).

## Problem and buyer

A technical team reviewing a filtered reconciliation candidate group may need to know whether a declared total is attainable, which original items form it, and whether several distinct selections do so. Equal amounts do not make item identities interchangeable. A single valid selection proves attainability; it does not identify the intended accounting match. A timeout, approximate NO, or solver satisfaction status does not supply an independently established exact negative or uniqueness certificate.

Prospective buyers are integration teams or reviewers who already own a reconciliation workflow. The initial module would process exported, explicitly modeled positive-integer groups. Currency scaling, signed adjustments, fees, dates, customer identities, tolerance and cross-statement exclusivity require separate model mappings. The prototype is an exact-selection diagnostic, with no ledger action or transaction approval.

## Existing alternatives and differentiation

Dynamics 365 already filters statements and bank documents through ordered matching rules, with an option to require manual selection for multiple amount matches. NetSuite also provides system/user rules and manual review when equally plausible candidates remain. These documents establish existing capabilities, not demand for this module or a missing vendor feature. [Microsoft matching-rule documentation](https://learn.microsoft.com/en-us/dynamics365/finance/cash-bank-management/set-up-bank-reconciliation-matching-rules), [NetSuite system-rule documentation](https://docs.oracle.com/en/cloud/saas/netsuite/ns-online-help/section_160374863744.html).

OR-Tools supports integer constraint models and existing solver statuses. The implemented baseline uses binary choices and one exact sum equality, without rounding. Public knapsack maximization under a capacity is a different model from exact target equality. [CP-SAT primary documentation](https://developers.google.com/optimization/cp/cp_solver), [knapsack primary documentation](https://developers.google.com/optimization/pack/knapsack).

The potential difference is a repeatable source/model/witness review with explicit ambiguity and unknown states around existing engines. The source compression discussion suggests preserving distinct-sum support, multiplicity and provenance as separate quantities. The implemented meet-in-the-middle compression is conventional; no algorithmic novelty, favorable general complexity or unique commercial position is demonstrated.

## What the finding could enable

1. A selection-assurance API with exact positive-integer inputs, stable original IDs, complete tiny counts, checked witnesses, explicit backend range and budget results.
2. A backend comparison harness that retains duplicate-value identities and distinguishes solver status from independently checked feasibility, negative evidence and solution count.
3. A source-resource/error planner that records main guards, unknown cutoffs, fallback behavior and conditional amplification requirements before a research backend is proposed.

These are overlapping modules within the shared evidence platform. Do not count them as three new customers or assume they inherit source algorithm proofs. A generic faster finance system or unrestricted low-memory framework remains deferred.

## Minimal architecture

Explicit model and candidate IDs -> exact integer validation -> existing solver or bounded conventional search -> original-ID and exact-sum witness check -> separate count/ambiguity result when exact enumeration completes -> source/resource/error report -> reviewer explanation. Preserve submitted candidate evidence separately from a new proposed selection. Amount equality alone is not a business-match decision.

The reference accepts two through 64 identified positive values and a nonnegative target, each below 2^256. Its optional equal-sum compression is safe across its disjoint halves: retain one representative witness and the number of original indexed subsets at each sum. In the low-space source representation, equal weights with different overlap masks cannot simply be merged because compatibility can differ. That broader representation is not implemented.

## Validation experiment

[2,294 reference/planner checks](../../snapshots/2026-10-08-baseline/subset-sum-reference-validation-2026-10-09-v1.json) cover all 1,089 positive value words 1..3 of lengths two through six, with 28,404 method/target queries against an independent binary-choice count oracle. Additional controls cover exact majority-error enumeration, guards, caps, invalid schemas, identities and 256-bit arithmetic. These finite tests accept no source proof or unrestricted backend.

In the generated 64-one target-32 fixture, compressed halves each retain 33 sums and peak at 98 simultaneously stored sum records, while preserving C(64,32)=1,832,624,140,942,590,534 distinct indexed selections. The occurrence method exhausts the same 50,000-record budget and reports unknown count and feasibility. This highly repeated fixture illustrates support compression, not a general speed or memory result. Native objects, sorting scratch/comparisons and input storage are outside the record/work accounting. [Saved repeat case](../../prototypes/subset-sum-repeated-64-2026-10-09-v1.json).

For values [5,5,10] with distinct IDs and target ten, the exact count is two: both five-valued items or the single ten-valued item. Repeating the same ID is refused. [Identity fixture](../../fixtures/subset-sum-duplicate-identities-2026-10-09-v1.json).

[150 live solver controls](../../snapshots/2026-10-08-baseline/subset-sum-solver-validation-2026-10-09-v1.json) cover 1,080 target queries on 117 tiny value words and ten generated integration cases. The CP-SAT adapter already finds checked feasible selections for the repeated and 32-distinct-power controls. Its satisfaction OPTIMAL status on [5,5,10] does not imply uniqueness. A budget-exhausted independent reference can still receive sufficient positive evidence from a directly checked proposal, while count remains unknown. The adapter deliberately caps the total and target at 2^62-1; larger exact Python integers are reported unsupported by that solver adapter, without scaling, truncation or floating conversion. [Saved existing-solver comparison](../../prototypes/subset-sum-existing-solver-comparison-2026-10-09-v1.json).

No comparative speed study, real accounting dataset, private customer input, proof check, source backend, finance deployment or buyer interview was completed.

## Technical and commercial limits

For n=64 and a conditional all-call witness-recovery error budget of 1/1,000,000, the planner assigns 261 odd-majority repetitions to each two-sided decision call; it conservatively reserves at most n+1 adaptive calls. The one-sided companion uses repeated OR. Both calculations require a genuine per-fixed-input error bound and fresh independent runs, neither validated by this planner. A final original-ID exact-sum check can confirm a positive witness; amplified NO remains probabilistic and must not be converted into exact infeasibility.

The low-space main program schedules u^120 rounds with two separately capped trials per round, each capped at u^500 * 2^ceil(n/2), where u=n+b+2. Thus the displayed trial-work cap is 2*u^620*2^ceil(n/2), aside from reset/scanning constants. It is an upper schedule, not a measured runtime lower bound; early successful YES runs may stop. Both source word models give wide words and charge multiword operations, with all relevant writable state counted for the space result. [Exact supplied-parameter plans](../../prototypes/subset-sum-source-schedules-2026-10-09-v1.json).

## Monetization hypothesis

Hypothesis: AUD 5,000 for a bounded selection/model-assurance assessment within the existing platform pilot. At 20 assumed specialist hours and AUD 180/hour, AUD 1,400 remains before sales/support/overhead; 30 hours cost AUD 5,400 and exceed the fee. These are assumed delivery economics, not quotes, demonstrated willingness to pay or revenue.

## Conditions to reject or defer

Reject this module if the vendor's existing ambiguity/review controls or ordinary solver already provide adequate evidence, candidate filtering makes ambiguity negligible, business-rule mapping dominates delivery cost, or counts do not change a real review decision. Defer a direct source backend until an actual implementation, evaluated cutoffs/resources, correctness/error mapping and useful benchmark exist. A modest ideal exponent improvement alone supplies no profitable product.

## Next concrete action

The concrete next business test is a read-only comparison on an authorized representative candidate-group export: measure preparation effort, item-identity mistakes, unsupported uniqueness/negative claims, reviewer decisions changed and incremental value over the incumbent workflow. Source numerical certificate, filtering/checksum/alias proof closure and low-space compression/representation/survival proofs need further review separately. [Current reading ledger](../../checkpoints/manuscript-ledger-2026-10-09-v8.json), [eighteen-contract registry](../../prototypes/curated-contracts-2026-10-09-v8.json).