A Worst-Case Subset Sum Algorithm Uses 2^(n/5) Space

For worst-case subset sum, the central question in the manuscript is not simply how quickly to find a solution. It is how much of the search must be kept in memory.

Given numbers a₁ through aₙ and a target t, the decision problem asks whether some choice of positions has values summing to t. Positions matter even when values repeat: with [3, 3, 5, 9], either occurrence of 3 is a distinct choice. The empty choice sums to zero. In general there are 2ⁿ possible subsets.

The manuscript gives a classical randomized decision algorithm. For inputs whose integer bit lengths are bounded by any fixed polynomial in n, it runs in polynomial time times 2^(n/2) and uses O_c(2^(n/5)) writable words. Each word has order n + b bits, where b bounds the bit length of the input integers and target. Both resource limits hold on every run. A solvable instance is answered YES with probability at least two thirds; the algorithm never answers YES incorrectly.

This is an asymptotic guarantee, not a practical speed claim. The contribution is a smaller memory requirement alongside half-exponential time—not the elimination of exponential search.

The starting point is meet-in-the-middle search. Split the positions in half, list the subset sums on each side, and look for two sums that add to the target. Each list has roughly 2^(n/2) entries. A classical improvement breaks the input into four quarter-sized parts: it stores quarter-sized lists and streams pair sums in sorted order, rather than retaining every pair. The search still takes half-exponential time, but the stored lists are smaller.

The new algorithm pushes this separation further: it generates information it does not keep. Its proof rests on two complementary cases, distinguished by how many distinct subset sums a block has. Two positions both carrying 3 have four indexed subsets but only three distinct sums: 0, 3, and 6. The manuscript measures this collision effect with deficiency: the number of positions in a block minus the base-two logarithm of its number of distinct sums. High deficiency means fewer distinct weights to retain; low deficiency means many distinct choices that may be useful in a different way.

The proof studies the mean deficiency of random blocks for a fixed input. The algorithm does not calculate that mean or decide which case applies. It runs both trials.

The compression trial divides positions into seven disjoint blocks and keeps only the distinct weights available from each block, together with the remaining raw positions. Because the blocks do not overlap, the algorithm can discard which particular subset produced a block weight. Small retained lists generate larger streams; a random prime groups left-side combinations by remainder, and the algorithm keeps one group at a time. If that group’s dictionary exceeds its hard capacity, it is skipped. The success argument needs only the group containing one fixed solution to fit. A remainder match is not enough for acceptance: the final sum must equal the target exactly.

The second trial handles the other case by giving a solution multiple possible representations and filtering those candidates. An exact sign-flip identity helps make a fixed solution uniformly distributed among subsets. Choose a random set of positions F, negate their values, subtract their original total from the target, and toggle those positions in the solution. At each flipped position, the contribution drops by that value whether it was included or excluded. Thus the transformed subset sums to the adjusted target, and toggling again recovers the original subset. Negating and shifting translates all subset sums without changing how many distinct sums there are.

The representation trial builds joins from small stored leaves through children to parents, using three disjoint “mixer” blocks for shared choices. Prescribed subset sizes and balanced background parts constrain the joins; nested modular filters discard many combinations while leaving some representations a chance to survive. Records must retain both their exact weight and their shared index mask. Equal weights cannot be merged indiscriminately: different masks can have different overlap with another parent.

The representation trial adds an overflow strategy. An extra prime can divide candidates into smaller buckets, but equal weights always remain together under the same congruence. If a right-side bucket still overflows, the algorithm splits it by successive mask bits and regenerates it. If it still exceeds capacity after every bit is fixed, the task is dropped. The proof separately bounds the chance that this process drops the path for one fixed solution.

The implementation applies each prefix restriction to the leaves before joining. A raw tuple therefore appears at only one prefix at each depth. With m shared positions, it can be processed at most m + 1 times, even if a later overlap test rejects it. This is a local accounting result, not the entire time bound: regenerating leaves and setting up streams also cost resources.

At the final test, the algorithm needs both disjoint masks and complementary exact weights. A separating set makes disjointness automatic by requiring left masks to lie inside it and right masks outside it. The manuscript samples separating families on four blocks and searches them depth first. The guarantee is for a fixed solution pair, not simultaneous coverage of all possible pairs. The resource analysis uses a full candidate-check schedule that ignores early success and the operation cap while retaining the overflow rules; that schedule does not depend on which families are sampled.

The proof roadmap fixes a surviving representation before exposing the extra prime and separating families. Since survival is rare, it subtracts an unconditional resource-failure bound rather than assuming typical resource use after conditioning on success. Bounded random sampling, an operation counter, and capped dictionaries enforce the limits even on unsuccessful runs. Independent rounds raise the success probability to at least two thirds. Small inputs and inputs outside the main branch use exact enumeration.

The explicit space bound is a polynomial factor times 2^(0.199n). Within each fixed polynomial bit-length class, the gap between 0.199 and 0.2 eventually absorbs that polynomial, yielding the stated O_c(2^(n/5))-word bound. At the 0.199 endpoint itself, the polynomial factor remains; the asymptotic conclusion is eventual and depends on the fixed bit-length bound.

The explainer notes that no matching formalization was available in the pinned manuscript context; its examples and local identities do not verify the complete algorithm. The claim is a specific theoretical one: generate what the search needs, retain less of it, and enforce the resource caps on every run.