Worst-case Subset Sum below the meet-in-the-middle bound
Worst-case Subset Sum below the meet-in-the-middle bound concerns the exponential running time of exact algorithms for Subset Sum: given n integers and a target, decide whether some subset sums to the target. The meet-in-the-middle algorithm of Horowitz and Sahni (1974) takes time about 2n/2, and for decades no worst-case algorithm with a smaller exponent was known. A manuscript dated 4 October 2026 in OpenAI's public mathematics collection (github.com/openai/math) claims a randomized algorithm with running time O(20.49n). Three days later, Ye and Li posted an O(20.499999n) algorithm obtained by a different approach, and later public work extends both. This page summarizes the published claims and lists related public work. Statements are the respective authors' claims; the publication of a paper, code or a certificate is not presented here as independent verification.
Background
- As recounted in the manuscript's introduction: Subset Sum appears as Knapsack in Karp's list of NP-complete problems. Horowitz and Sahni's meet-in-the-middle algorithm lists the subset sums of two halves of the input and searches for complementary sums, which gives the 2n/2 time scale. Schroeppel and Shamir kept that time scale while reducing the space exponent to 1/4. Chen, Jin, Randolph and Servedio obtained randomized worst-case time O(2n/2n−γ) for a constant γ > 0.5023. The manuscript distinguishes such polynomial-factor savings from a fixed reduction of the exponent below 1/2.
The original result
- Claim. There is a uniform randomized classical algorithm for Subset Sum in a word-RAM model with word length of order n + b, where b is the largest bit length of the input integers and the target. It halts on every execution and answers correctly with probability at least 2/3. For every fixed c, inputs with b ≤ nc are processed in O(20.49n) word operations on every outcome of the random choices (Theorem 1.1); the intermediate bound is 20.489995n times a polynomial factor. No assumption is made on the distribution of the input.
- Sources (openai/math repository, commit
1581d4c):- Subset Sum in Time O(20.49n) (4 October 2026);
- A Low-Space Algorithm for Worst-Case Subset Sum (26 September 2026): poly(n)2n/2 time with O(2n/5) writable words and one-sided error.
- Formalization. The repository has no Lean scope note for this family (checked 16 October 2026).
Related work by others
| Date | Work | Relation | Public claim | Public status (checked 16 October 2026) |
|---|---|---|---|---|
| 2026-10-07 | Lixi Ye and Baitian Li, arXiv:2610.10446 (v1), Subset Sum via Partial Match | Parallel result | Subset Sum in time O(20.499999n) (Theorem 4.1 gives the exponent 1/2 − 1/450000), breaking the meet-in-the-middle bound with the representation technique of Randolph and Węgrzycki and a depth-2 linear circuit for the partial match problem, through the framework of Alman and Li. | arXiv preprint, version 1. Its declaration cites OpenAI's manuscript as a result of a similar type and states that the result was developed independently by a different approach. Its AI disclosure credits GPT-6 Pro with a circuit construction (5 September) and GPT-6 astra ultra with the reduction to ordinary Subset Sum (28 September). |
| 2026-10-11 | Swapnil Jain, Swapnil-jain/subsetsum-derand (GitHub) | Related (deterministic algorithms) | Deterministic Subset Sum below 2n/2: a non-explicit bound with exponent at most 0.4986298 and an explicit one with exponent at most 0.4999983, built on Ye and Li's work and on the reduction recorded in their AI disclosure. The README credits an audit of where OpenAI's construction uses randomness for its covering tool, and states that the package does not derandomize that construction. | GitHub repository, described as a preprint that is not peer reviewed. It reports internal referee passes and Lean 4 checks of certificate inequalities. |
| 2026-10-15 | conorholds/subset-sum-bounds (GitHub) | Extension (conditional parameter study) | An open collaborative project on OpenAI's randomized construction. It reports interval-checked numerical witnesses for retuned parameters: exponent budgets 0.48981 with the manuscript's filters and 0.48976 with degree-10 filters, conditional on the manuscript's qualitative algorithmic arguments. | GitHub repository. The README describes the result as an initial research candidate, not an established new running-time record, and states that the full algorithmic argument still needs independent review. |
| 2026-10-15 | Annanay Kapila, Hexagon 2610.00261 (v1), Subset Sum in time O(20.4877n) | Extension | A randomized algorithm with running time O(20.4877n). It keeps the manuscript's framework (isolation, a capped preliminary search, a modular checksum and alias subtraction) and replaces two components: an alias procedure that computes phase sums with a smaller modulus, and a family of 43 checksum filters chosen according to the input pattern. Numerical certificates in Arb ball arithmetic cover the alias constraints and 430 moment inequalities. | Hexagon preprint, version 1, labelled as primarily AI-generated text with human understanding of some parts. Its provenance statement says that the argument relies on results of OpenAI's manuscript and that the numerical checks and a ChatGPT review do not constitute formal verification of the complete proof. |
Notes
- Chen, Mao and Zhang (arXiv:2610.12953, October 2026) treat a different regime: time near-linear in the largest input integer, not an exponent in n.
- Dates are those shown by arXiv, Hexagon, GitHub and the manuscript. The list covers sources found up to the date above; it makes no priority or completeness claim.