Not evaluated
Subset Sum in O(2^(0.49n)) time (family 138)
The gist
On October 6, 2026, OpenAI announced, for Subset Sum (finding numbers that add up to a given total), an O(2^(0.49n)) time algorithm from an unreleased internal model.
DiscoverIA status on October 12, 2026: not evaluated, meaning no third-party evaluation found.
AI draft, not reviewedWhat has not been reviewed?
Text written by an AI (DiscoverIA pipeline), on . The status and its sources come from the registry; only the explanatory text has not been reviewed. A reported error is corrected, then the text is reviewed.
Cite this entry
A single status snapshot since Oct 12, 2026: a citation always points to a dated snapshot.
Cite snapshot 1, Oct 12, 2026
APA citation with the dated link
BibTeX @misc, key discoveria-oai-fam-138-subset-sum-o-2-0-49n-time-r1
@misc{discoveria-oai-fam-138-subset-sum-o-2-0-49n-time-r1,
author = {{DiscoverIA}},
title = {Subset Sum in O(2^(0.49n)) time (family 138)},
howpublished = {DiscoverIA registry, entry oai-fam-138-subset-sum-o-2-0-49n-time},
note = {Status “Not evaluated”, snapshot 1, recorded on October 12, 2026. New result},
year = {2026},
url = {https://discoveria.ai/entry/oai-fam-138-subset-sum-o-2-0-49n-time#releve-1},
urldate = {2026-10-12}
}Dated link opens this snapshot in the history
To understand ≈ 20 s reading time, estimated
What it changes
If the manuscript were correct, the algorithm's worst-case running time would be at most 2^(0.49n) up to a constant, where n is the number of values supplied: an upper bound, not an exact running time.
What remains unclear
No Lean proof (checkable by computer) is supplied for this family, and no third-party assessment is recorded. The sources read do not say where the question stood before the announcement.
For experts
Sources, method, key facts, status history, report an error
Status
Not evaluated
Recorded on · github.com · README.md
Step 1 of 4 on the scale: not evaluated. Next step: under review.
- Announced
- Recordednot evaluated
- nextTo follow
What this status means
Source reading : Source read word for word (level 3 of 3)
The result is declared neither right nor wrong.
To move to “Under review”: a public review under way. To “Peer reviewed”: a journal publication or a review by named experts.
Sources
- Main sourcegithub.com · CONTENTS.mdlink only, reading not recorded
- Repositorygithub.com · Subset-Sum-in-Time-2…link only, reading not recorded
- Repositorygithub.com · A-Low-Space-Algorithm-for…link only, reading not recorded
Method
In the openai/math repository, family 138 comprises two manuscripts: "A Low-Space Algorithm for Worst-Case Subset Sum" (September 26, 2026) and "Subset Sum in Time O(2^(0.49n))" (October 4, 2026). The absence of Lean is inferred from the absence of a lean/docs file for this family; OpenAI's README states that not all manuscripts have a Lean formalisation. No revision of these manuscripts is reported in history.md. DiscoverIA status: not evaluated, meaning that no third-party evaluation has been found in the sources read. Set on October 12, 2026 from github.com (page read, quotation checked word for word: “Not all have accompanying Lean formalizations.”).
Limits
DiscoverIA has not checked this result itself.
Key facts
- Claimed by
- OpenAI (unreleased internal model)
announced on Oct 6, 2026 - Nature
- new result
- Field
- Theoretical computer science
- In openai/math
- family 138, section “Theoretical computer science”, 2 manuscripts dated Sep 26, 2026
- Lean proof
- none supplied
- Revisions
- none reported by the claimant
- Checked by
- no verifier identified
- Sources
- 3 : 3 links only
- This entry
- AI draft, not reviewed
Status history
Only one observation so far.
- 01
First observation:Not evaluatedCurrent status
Family with no Lean proof supplied. No third-party evaluation read.
Source: github.comread word for word
An observation is added; none is ever erased.
In the same set
openai/math: 719 manuscripts in 372 families from an unreleased internal model · entry 134 of 372, by family number
- Not evaluated : Sharp homogeneous depth-five complexity of matrix products (family 135)
- Not evaluated : The quasilinear PCP-for-PPAD conjecture (family 136)
- Not evaluated : One-tape time simulation in two-fifths-power space (family 137)
- Not evaluated : Subset Sum in O(2^(0.49n)) time (family 138)
- Not evaluated : Subpolynomial queries for log-concave sampling (family 139)
- Not evaluated : Memory–sample lower bounds for noiseless Gaussian regression (family 140)
- Not evaluated : The existential theory of the reals and existential–universal sentences in the counting hierarchy (family 141)
Report an error or suggest a source
Thank you, your message was sent.
Sending failed. Try again, or write to contact@discoveria.ai.
Is your result listed?What each status requires, correcting this entry, replying to it.