Subset Sum in O(2^0.49n) time

What OpenAI claims

Gives a uniform randomized classical algorithm for worst-case Subset Sum in ordinary O(2^0.49n) word-RAM time on polynomial-bit inputs, where n counts the integers. The time bound holds on every execution and success probability is at least 2/3 on every input. Inputs may repeat positive integers; words have O(n+b) bits for maximum input bit length b.

Papers (2)

1. Subset Sum in Time O(2^0.49n)

   4 October 2026 · Preprint, not peer reviewed · PDF

   We give a uniform randomized classical algorithm for Subset Sum with bounded error and worst-case running time O(2^0.49n) on polynomial-bit inputs in a word-RAM model, where n is the number of input integers. The time bound holds on every random execution.

2. A Low-Space Algorithm for Worst-Case Subset Sum

   26 September 2026 · Preprint, not peer reviewed · PDF

   We give a uniform classical randomized decision algorithm for worst-case Subset Sum. Under every fixed polynomial bound on input-integer bit length, it uses poly (n)2^n/2 time and ordinary O(2^n/5) writable words of O(n+b) bits, where b is the largest input bit length. Both resource bounds hold on every execution. The error is one-sided: the algorithm always rejects unsolvable instances and accepts each solvable instance with probability at least 2/3.

Status

Preprint. The papers have not been independently reviewed. Treat the result as OpenAI's claim until other mathematicians have checked it. If a video exists, it illustrates the statement; it is not the proof.