Subset Sum

Given positive integers $a_1,\ldots,a_n$ and a nonnegative target $t$ , decide whether a subset sums to $t$ ; repeats and the empty subset are allowed. For $n\ge2$ , let $b$ be the maximum input or target bit length. A single randomized word-RAM program uses $w=\lceil4(n+b+\log_2(n+2))\rceil$ -bit words, halts on every run and is correct with probability at least $2/3$ on each input.

Classic bound: $O^*(2^{n/2})$ (Horowitz and Sahni 1974).

Full computation rules

Word reads and writes, indirect addressing, comparison, arithmetic (including multiplication, division and remainder), bitwise operations, shifts and independent uniform random words each cost one operation. Overflow costs multiple operations. Retained random words use memory. All input access and preparation count; the program has no advice or external tables. For each fixed $c$ and $b\le n^c$ , the bound holds for every random outcome, and the program does not depend on $c$ .

The bound has the form $O(2^{\alpha n})$ . $\alpha$ is the time exponent; lower is better.

What counts as Claimed: Published results for this problem without a qualifying repository review or Lean proof check.
What counts as Human Verified: This problem has no community repo with a qualifying review rule.
What counts as Lean Verified: A result shows here when we rebuild its Lean proof from source and check, with the Lean kernel, that it proves our exact problem statement.

Claimed Human Verified Lean Verified

Rank	Bound	Evidence levelLevel	Player	Date	Link
1	$O(2^{0.49n})$	First breakthrough	openai	Oct 6	Source	openai Oct 6

$\alpha$ in $O(2^{\alpha n})$ , lower is better $\alpha$ in $O(2^{\alpha n})$ linear scale, lower is better

ClaimedHuman VerifiedLean Verified

First breakthrough

\alpha

(linear scale)

\alpha=0:\ O(1)

Relevant repos

openai/math

α\alphaα in O(2αn)O(2^{\alpha n})O(2αn), lower is betterα\alphaα in O(2αn)O(2^{\alpha n})O(2αn)linear scale, lower is better

Relevant repos iWe list repositories that publish a result for this problem or accept improvements to it. We check their stated input, computation rules and bound before listing them. A listing does not imply that we checked their proof.

$\alpha$ in $O(2^{\alpha n})$ , lower is better $\alpha$ in $O(2^{\alpha n})$ linear scale, lower is better

Relevant repos