# Subset sum reconciliation backend

Edition: 8 October 2026. Initial decision: **Conditional research**. The product interpretation and pricing are hypotheses; independent proof and buyer validation remain open.

## Research finding

The subset-sum paper claims worst-case O(2^(0.49n)) randomized word time on polynomial-bit positive-integer inputs, compared with the familiar half-exponent scale. The running-time constants and crossover remain to be established; no family scope document is listed.

## Problem and buyer

A reconciliation system may need to find which bounded set of integer-valued items adds to a known total. Large ambiguous groups can make exact search expensive.

## What the finding could enable

A backend could improve worst-case search for a carefully filtered candidate group if the exponent saving appears at realistic sizes. It enables a potentially stronger exact-search component; full accounting reconciliation needs additional evidence and business rules.

## Technical and commercial limits

The problem remains exponential. Currency must be represented as exact scaled integers. Tolerances, negative adjustments, dates, duplicate identities and explanatory priorities change the practical problem. A decision algorithm may require self-reduction to return a witness.

## Minimal architecture

Candidate filter -> exact-integer normalization -> search backend -> independently verified witness -> explanation record. Never change ledger data or approve transactions automatically as part of the research prototype.

## Existing alternatives and differentiation

Existing exact search, meet-in-the-middle and integer-programming methods are the baseline. A usable improvement must include memory and preprocessing, not only an exponent comparison.

## Monetization hypothesis

Hypothesis: AUD 4,000-15,000 for an offline reconciliation benchmark or integration. Price depends on handling a demonstrated unresolved workload; no financial return is established.

## Validation experiment

Benchmark n, input bit length, repeated values and adversarial distributions against exact references. Verify every returned subset sum and measure correct negative decisions with known fixtures.

## Conditions to reject or defer

Reject if candidate filtering already reduces n enough for current methods, or research overhead eliminates the modest exponent benefit.

## Next concrete action

Read the witness-recovery and low-space companion constructions; quantify the ideal exponent saving separately from any implementation result.

## Source evidence

Repository sources are pinned to revision `fd4aeeb2ee4fc729c18d98444fed42fd0529eeeb`. Selected scope notes and manuscript statements have been reviewed to the extent described above; these links do not represent successful kernel checks.

### Family 138

Subject: Subset Sum in $`O(2^{0.49n})`$ time.

- [Subset Sum in Time $`O(2^{0.49n})`$ ](https://github.com/openai/math/blob/fd4aeeb2ee4fc729c18d98444fed42fd0529eeeb/preprints/Subset-Sum-in-Time-2-power-0-49n-October-4-2026/subset-sum.pdf)
- [A Low-Space Algorithm for Worst-Case Subset Sum](https://github.com/openai/math/blob/fd4aeeb2ee4fc729c18d98444fed42fd0529eeeb/preprints/A-Low-Space-Algorithm-for-Worst-Case-Subset-Sum-September-26-2026/paper.pdf)

## Current alternative sources

Primary documentation reviewed on 8 October 2026. Product availability demonstrates alternatives, not demand or willingness to pay for this proposal.

- [Gurobi commercial licensing](https://www.gurobi.com/product/pricing-and-licensing)