OpenAI groups related papers into a “family”. OpenAI’s catalogue describes this one:
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.
The release has no Lean statement for this family, so there is no formal statement to compare with the result described above.
Possible match to OpenAI’s description, selected from the papers’ main statements because it shares the most wording. No review confirming the selection is recorded.
The other possible matches are Theorem 1.1 in A Low-Space Algorithm for Worst-Case Subset Sum () and Corollary 1.2 in A Low-Space Algorithm for Worst-Case Subset Sum ().
There is a uniform randomized classical algorithm \mathcal A for Subset Sum with the following properties in the word-RAM model (1.1). For every input with n\ge2, the algorithm halts on every execution and outputs the correct answer with probability at least 2/3. For every fixed positive integer c, there are constants C_c>0 and N_c\ge2 such that every input with n\ge N_c and b\le n^c is processed, on every outcome of the random choices, in at most
C_c\,2^{0.49n}
word operations. The program is not given c and does not depend on c.
Reported proof verification
The release has no Lean statement for this family. The papers are available to read and assess.
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.
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 \(\mathop{\mathrm{poly}}\nolimits (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.
Lean statements
The release has no Lean statement for this family. Its papers remain available to read, and contributors can propose a formal statement of a result. Suggest a change
Independent comparisons and proof-verification reports
Does the Lean express the advertised result?
The release contains no Lean statement for this family, so there is no formal statement to compare with OpenAI’s description.
Other proofs and exact calculations
These reports examine claims in the papers using exact calculations for finite claims, independently of the release’s Lean proofs. Read each report for the exact claim it covers.
“CERTIFIED” Exact code written independently from the paper confirms that the published object has the claimed property.
What it covers
“a finite component: the numerical certificate of Proposition prop:filtering-moments (Appendix app:numerical) - every printed enclosure, error bound and comparison recomputed in directed rational interval arithmetic; the analytic trapezoid estimate, contour shifts and Parseval monotonicity are read, not run, and the O(2^0.49n) algorithm is theory”
What these papers cite in the release, and what cites them
These links come from the papers’ bibliographies. A citation records that one paper cites another; how each cited result is used has not been examined here.
Papers elsewhere in the release that this family’s papers cite
This family’s papers cite no paper elsewhere in the release.
Papers elsewhere in the release that cite this family’s papers
No paper elsewhere in the release cites this family’s papers.
References outside the release
Each paper’s outside references are listed with it on its reading page, where each citation is placed. Every outside work cited in the release: References outside the release
Explain a result, compare statements or propose a correction
Atlas has no contributed explanation for this family yet. You can offer one with a GitHub account. You receive named credit and disclose any AI assistance.
Each button opens a GitHub form with this page and its source version filled in. Opening the form does not reserve the work.
Commentary on this family by others, dated and credited. It is commentary, not a finding.
An unsigned public tier list, the OpenAI Math Tier List, classes it as a algorithm and rates its significance, if it holds up, as “Career-defining publication”. The page says that nothing on it is verified.
Each item identifies a statement, definition or report that needs further review. Its link opens a GitHub form with the source version already recorded.
Identify the theorem the catalogue describes
Family 138The theorem shown was selected from shared wording with OpenAI’s description. Atlas records no review confirming that it is the theorem the description means.Open the form
State the result in Lean
Family 138The release has no Lean statement for this family.Open the form
Why this passage is shown
Theorem 1.1
In A Low-Space Algorithm for Worst-Case Subset Sum, 26 September 2026
How it was found
Its words were compared with the words of OpenAI’s catalogue description.
Words they share
algorithm, classical, integers, least, positive, probability, randomized, uniform, words
Review
Atlas records no review confirming that this is the theorem OpenAI’s description refers to.
Exact calculations for finite claims, cert-machine
Their verdict
“CERTIFIED”
Claim tested or proved
Exact code written independently from the paper confirms that the published object has the claimed property.
What it covers
“a finite component: the numerical certificate of Proposition prop:filtering-moments (Appendix app:numerical) - every printed enclosure, error bound and comparison recomputed in directed rational interval arithmetic; the analytic trapezoid estimate, contour shifts and Parseval monotonicity are read, not run, and the O(2^0.49n) algorithm is theory”