Not evaluated
Exponential state costs for two-way automata (family 129)
The gist
On October 6, 2026, OpenAI announced two manuscripts claiming exponential lower bounds on the number of states of two-way automata.
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-129-exponential-state-costs-two-way-automata-r1
@misc{discoveria-oai-fam-129-exponential-state-costs-two-way-automata-r1,
author = {{DiscoverIA}},
title = {Exponential state costs for two-way automata (family 129)},
howpublished = {DiscoverIA registry, entry oai-fam-129-exponential-state-costs-two-way-automata},
note = {Status “Not evaluated”, snapshot 1, recorded on October 12, 2026. New result},
year = {2026},
url = {https://discoveria.ai/entry/oai-fam-129-exponential-state-costs-two-way-automata#releve-1},
urldate = {2026-10-12}
}Dated link opens this snapshot in the history
To understand ≈ 30 s reading time, estimated
What it changes
A two-way automaton is a machine with a finite number of states that reads its input in both directions; to complement it is to build a machine that accepts what the first one rejects. According to their titles, the manuscripts concern the number of states needed to complement a nondeterministic automaton, and for “one-way liveness” with a deterministic automaton, both two-way. If the manuscripts were correct, that number would be at least exponential in both cases.
What remains unclear
The Lean (a language in which a computer checks every step of a proof) is supplied by OpenAI itself and marked “unchecked” in formalization.yaml. No third-party verification is recorded. 3 Comparator statements accompany the 2 manuscripts, and the sources read do not say how they relate to them.
For experts
Sources, method, key facts, status history, report an error
Status
Not evaluated
Recorded on · github.com · 129.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 · An-exponential-state…link only, reading not recorded
- Repositorygithub.com · An-exponential-two-way…link only, reading not recorded
- Lean proofgithub.com · 129.mdpage read word for word
- Lean proofgithub.com · OneWayLiveness.leanlink only, reading not recorded
- Lean proofgithub.com · TwoWayComplementation.leanlink only, reading not recorded
- Lean proofgithub.com · TwoWayDeterminization.leanlink only, reading not recorded
Method
The openai/math repository contains 2 manuscripts dated September 25, 2026. The first is titled “An exponential state lower bound for two-way nondeterministic complementation”. The second is titled “An exponential two-way deterministic state lower bound for one-way liveness”. OpenAI attaches lean/docs/129.md lean/ComparatorChallenges/OneWayLiveness.lean, lean/ComparatorChallenges/TwoWayComplementation.lean and lean/ComparatorChallenges/TwoWayDeterminization.lean. According to history.md, no revision is reported. 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: “describes the scope of the Lean formalization”).
Limits
No named third party: the recorded checks come from the claimant or from a platform tool. The claimant supplies a Lean proof; as of this date, DiscoverIA has found no independent verification of this proof or of the result.
Key facts
- Claimed by
- OpenAI (unreleased internal model)
announced on Oct 6, 2026 - Nature
- new result
- Field
- Theoretical computer science
- In openai/math
- family 129, section “Theoretical computer science”, 2 manuscripts dated Sep 25, 2026
- Lean proof
- supplied by the claimant, marked “unchecked” (not reviewed) in its repository
- Revisions
- none reported by the claimant
- Checked by
- claimant (Lean supplied, not checked by a third party)
- Sources
- 7 : 1 read word for word, 6 links only
- This entry
- AI draft, not reviewed
Status history
Only one observation so far.
- 01
First observation:Not evaluatedCurrent status
Family with a Lean proof supplied by the claimant. No third-party check read; the source marks this proof as not reviewed (“unchecked”).
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 125 of 372, by family number
- Not evaluated : Exponential semidefinite complexity of perfect matching (family 126)
- Not evaluated : The asymptotic Gotsman–Linial conjecture (family 127)
- Not evaluated : A factor-two approximation for shortest common superstring (family 128)
- Not evaluated : Exponential state costs for two-way automata (family 129)
- Not evaluated : Fourier transforms below n log n (family 130)
- Not evaluated : Polynomial mixing of graph switches with prescribed degrees (family 131)
- Not evaluated : A counterexample to the quadratic sensitivity conjecture (family 132)
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.