HEXAGONbeta

A certified exponent of 0.48758 for worst-case Subset Sum, and limits of the alias–checksum analysis

A mix of human-written and AI-generated textHuman understanding: some partscs.DS — Data Structures and Algorithmscs.CC — Computational Complexity

Contributed by Jennifer Voitle ↗

Version 1 / Nov 07, 2026 / CC BY 4.0

Abstract

For more than fifty years, since Horowitz and Sahni's meet-in-the-middle algorithm of 1974, the best exponent for worst-case Subset Sum was 1/21/2. In October 2026 that barrier fell twice within a week, with OpenAI's 20.49n2^{0.49n} algorithm and, independently, Li and Ye's 2(1/2−1/450000)n≈20.4999978n2^{(1/2 - 1/450000)n} \approx 2^{0.4999978n}, and improvements have followed quickly since: within three weeks A. Kapila's modification of the OpenAI approach ("Base") reached 0.4877, a retuning of Base by JoshuaQFEX reached 0.487676, and a refinement by Y. Bills reached 0.4876723. Here we push this line of work further and examine what limits it. Conditional on the cited non-numerical proofs, we give a certified parameter point with threshold T=0.4875754036T=0.4875754036: for every fixed T′>TT'>T, the uniform randomized algorithm uses O(2T′n)O(2^{T'n}) word operations on inputs of polynomial bit length, with success probability at least 2/32/3. In particular, it runs in time O(20.4875755n)O(2^{0.4875755n}). A single asymmetric filter replaces Base's family of 43 filters. Independent interval computations certify all required numerical conditions, including both filtering moments and their quadrature errors. We prove a lower bound on the first filtering moment, valid for all positive continuous densities, that excludes every parameter choice with τ≤0.484\tau\le0.484 in the original OpenAI proof's sufficient budget. Three algebraic bounds explain the costs at our improved point. Separately, an enumeration phase that inserts at least 2(1−η−o(1))n2^{(1-\eta-o(1))n} alias classes, spending a counted step on each, and uses checksum gap at most Δ\Delta needs exponent at least (1−Δ)/2(1-\Delta)/2. This is a conditional operation-count bound; a global upper bound on achievable checksum capacity remains open. Finally, we isolate a small-layer statement that would yield threshold 0.48734075280.4873407528, prove combinatorial special cases, and identify the remaining questions.

Author comments: 30 pages, 2 figures. The main result is conditional on the written proofs of OpenAI (4 Oct 2026) and A. Kapila (commit 44c34961); its numerical conditions are certified in interval arithmetic. The companion file SECTION_T_v3.pdf (full proofs of the ternary alias step, Appendix A) is included with the source. Code, certificates, verification scripts and a timestamped research record: https://github.com/jv1000/subset-sum. AI use is described in Section 11.

Provenance statement

This paper was produced by the author working with AI systems over about three weeks (October–November 2026). The author chose the research directions, decided which ideas to pursue or drop, set the verification standards, and organized independent checks of every result; she takes full responsibility for the content. Tools and roles: - Claude (Anthropic; Claude Opus5.5, used through the Claude app with code execution and through Claude Code on the author's computer) carried out much of the computation and analysis: the interval-arithmetic certifications, the block-count audit, Lemma 1, the 16-block point, the certified point of Theorem 1, and the analysis of the costs and the counting floor. It also drafted most of the manuscript text, which the author directed, challenged and edited. - Claude Fable 5.1 (Anthropic) was the second independent reviewer, a collaborator on the ternary alias step (the companion Section T) and on the reduction of the small-layer statement [S], and gave one independent re-derivation of Base's probabilistic core. - Astra 6 (an OpenAI-based assistant) did the landscape study of the original OpenAI construction and outside checks, reviewed the ternary step, gave a second re-derivation of Base's core, supplied proofs of special cases in Appendix B, refereed the whole manuscript, and produced a further independent interval certificate of all three parameter points. - Software: python-flint (Arb ball arithmetic, 200 bits), mpmath interval arithmetic, NumPy/SciPy for floating-point exploration, and LaTeX. How the work was checked: - Every certified numerical claim was computed by at least two independently written implementations in rigorous ball/interval arithmetic, with analytic bounds on quadrature error. - Experiments were pre-registered (prediction and a control written down before running), and floating-point results are labelled as evidence, not proof. - Reviewers were run in fresh contexts, separate from the work they checked; a system that built a result never refereed it. A fresh Claude context re-derived Corollary D from its statement alone. - Every error found, including the reviewers' findings, is logged with its correction. None changed a certified claim. - The research record (code, certificates, reviews, all revisions) is public at https://github.com/jv1000/subset-sum, with SHA-256 manifests timestamped via OpenTimestamps at five points during the work. Not yet done: the main result is conditional on the non-numerical lemmas of the OpenAI paper and of A. Kapila's written proof, which were read and partly re-derived by AI reviewers but not independently verified by a human expert. No part has been formalized in Lean. Independent human verification of the new proofs (Lemma 1, Proposition 1, the Appendix B cases and the companion Section T) is ongoing, independent verification by a human expert has not yet been completed.

References

  1. E. Horowitz and S. Sahni. Computing partitions with applications to the knapsack problem. J. ACM 21(2):277--292, 1974. doi:10.1145/321812.321823.DOI
  2. R. M. Karp. Reducibility among combinatorial problems. In Complexity of Computer Computations , pp. 85--103. Plenum, 1972.
  3. R. Schroeppel and A. Shamir. A T=O(2n/2)T = O(2^{n/2}), S=O(2n/4)S = O(2^{n/4}) algorithm for certain NP-complete problems. SIAM J. Comput. 10(3):456--464, 1981. doi:10.1137/0210033.DOI
  4. X. Chen, Y. Jin, T. Randolph and R. A. Servedio. Subset Sum in time 2n/2/poly(n)2^{n/2}/\mathrm{poly}(n). In APPROX/RANDOM 2023 . arXiv:2301.07134 (https://arxiv.org/abs/2301.07134) [cs.DS].arXiv
  5. X. Chen, Y. Jin, T. Randolph and R. A. Servedio. Average-case subset balancing problems. In SODA 2022 , pp. 743--778. SIAM, 2022.
  6. T. Randolph and K. Węgrzycki. Beating meet-in-the-middle for subset balancing problems. In STOC 2026 , pp. 1314--1325. ACM, 2026. doi:10.1145/3798129.3800841.DOI
  7. P. Austrin, P. Kaski, M. Koivisto and J. Nederlof. Dense Subset Sum may be the hardest. In STACS 2016 . arXiv:1508.06019 (https://arxiv.org/abs/1508.06019) [cs.DS].arXiv
  8. J. Nederlof and K. Węgrzycki. Improving Schroeppel and Shamir's algorithm for Subset Sum via orthogonal vectors. In STOC 2021 . arXiv:2010.08576 (https://arxiv.org/abs/2010.08576) [cs.DS].arXiv
  9. B. Li and L. Ye. Subset Sum via Partial Match. arXiv:2610.10446v2 (https://arxiv.org/abs/2610.10446v2) [cs.DS], 7 Oct 2026, revised 2 Nov 2026.arXiv
  10. OpenAI. Subset Sum in time O(20.49n)O(2^{0.49n}). OpenAI Math Release preprint, 4 Oct 2026. https://github.com/openai/math/tree/main/preprints/Subset-Sum-in-Time-2-power-0-49n-October-4-2026.link
Show all 20 referencesShow fewer references
  1. A. Kapila (a-kapila). subset-sum/PROOF_0.4877.tex , https://github.com/a-kapila/maths-proofs, commit 44c34961, 14 Oct 2026. Cited as Base.link
  2. J. Wharton (JoshuaQFEX). subset-sum-bound, https://github.com/JoshuaQFEX/subset-sum-bound, commit bed8e18, 20 Oct 2026.link
  3. Y. Bills (yannouli). subset-sum-conditional-refinement, https://github.com/yannouli/subset-sum-conditional-refinement, v1.0.0, 21 Oct 2026, and v1.1.0 (verification supplement), commit 590bb68, 22 Oct 2026.link
  4. Astra (an OpenAI-based assistant working with the author). Round 5 landscape and 0.48 constraint audit, Nov 2026. Files E2_LANDSCAPE.md and target_048 . Included in the repository (Section 11).
  5. L. N. Trefethen and J. A. C. Weideman. The exponentially convergent trapezoidal rule. SIAM Review 56(3):385--458, 2014. doi:10.1137/130932132.DOI
  6. J. B. Rosser and L. Schoenfeld. Approximate formulas for some functions of prime numbers. Illinois J. Math. 6:64--94, 1962.
  7. N. Howgrave-Graham and A. Joux. New generic algorithms for hard knapsacks. In EUROCRYPT 2010 , LNCS 6110, pp. 235--256. Springer, 2010. doi:10.1007/978-3-642-13190-5_12.DOI
  8. A. Becker, J.-S. Coron and A. Joux. Improved generic algorithms for hard knapsacks. In EUROCRYPT 2011 , LNCS 6632, pp. 364--385. Springer, 2011. doi:10.1007/978-3-642-20465-4_21.DOI
  9. N. Alon, R. Yuster and U. Zwick. Color-coding. J. ACM 42(4):844--856, 1995.
  10. M. L. Fredman and D. J. Volper. The complexity of partial match retrieval in a dynamic setting. J. Algorithms 3(1):68--78, 1982.

Version history

  1. v1 · 30 pagesSubmitted by Jennifer Voitle30 pages, 2 figures. The main result is conditional on the written proofs of OpenAI (4 Oct 2026) and A. Kapila (commit 44c34961); its numerical conditions are certified in interval arithmetic. The companion file SECTION_T_v3.pdf (full proofs of the ternary alias step, Appendix A) is included with the source. Code, certificates, verification scripts and a timestamped research record: https://github.com/jv1000/subset-sum. AI use is described in Section 11.CurrentNov 07, 2026