A polynomial-time factor-2 approximation for shortest common superstring (the question behind the Tarhio-Ukkonen greedy conjecture)
Given a finite set of strings, the shortest common superstring problem asks for a shortest string containing every member of as a contiguous substring; it is NP-hard and MAX-SNP-hard. Tarhio and Ukkonen (1988) conjectured that the greedy maximum-overlap merging procedure is a 2-approximation. Proven guarantees improved from 3 (Blum, Jiang, Li, Tromp, Yannakakis) through 2.5 (Sweedyk), (Mucha) and below 2.466 (Englert, Matsakis, Vesely), with factor 2 the long-standing target. Is there a polynomial-time algorithm that always outputs a common superstring of length at most twice the optimum (in particular, is greedy one)?
- Result
- Proved(see note)
- Status
- Variant only
- AI contribution
- AI-discovered
- Method
- Argument
- Field
- Approximation algorithms; string algorithms
- Posed by
- Jorma Tarhio and Esko Ukkonen (greedy factor-2 conjecture); the algorithm-independent factor-2 question is cited in the manuscript without a named poser
- Year posed
- 1988
- Years open
- 38y
- Solved
- 2026-09-24
- Model
- Unreleased internal OpenAI model
- Vendor
- OpenAI
- Collaborators
- —
- Verification
- Lean-checked, statement unaudited
- Publication
- Announced
- Collection
- OpenAI math release (October 2026), version adc7f12
- Significance
- 35 / 100
- Disclosed cost
- —
- Wikipedia
- No dedicated article
What was actually shown
Theorem 1.1: a deterministic algorithm, polynomial in the total encoded input size (including symbol labels), outputs for every finite family of explicitly represented strings a common superstring with . The proof builds a balanced hierarchical graph on all substrings from forced occurrence counts (a lower bound on the optimum), decomposes it into periodic layers and connects them at extra cost at most . It does not show that Greedy or the Collapsing procedure attains factor 2 (Greedy is reported false by Shibata 2026), and gives nothing below factor 2. An August 2026 preprint of Chukhin, Kulikov, Mihajlin and Smal reported .
What the AI did
The release README says the vast majority of results were obtained with one fixed procedure using an unreleased internal OpenAI model, on average about three hours of ChatGPT Pro thinking compute per result, and that some outputs build on earlier results produced by the models. This result is not among the README's exceptions (the Hodge conjecture for CM abelian varieties and the Re(s) > 11/12 zero-free region, whose write-up was human edited). The manuscripts are authored 'OpenAI' and name no human author. The family is a single manuscript (September 24, 2026), with a Lean formalization listed in the release's formalization catalogue.
Verification
No independent mathematician has checked this yet. Checked here: Theorem 1.1 was read against the factor-2 question. The guarantee is for a new algorithm, not Greedy; the manuscript itself cites a September 2026 preprint (Shibata) reporting a counterexample to the Greedy conjecture with ratio at least 9/4. Lean: formalization.yaml lists OAI.Superstring.main (lean/OAI/Computability/Superstring/Main.lean, comparator Superstring.json). Its statement was read here: there is a function on instances with a polynomial-time finite-alphabet Turing machine implementation in the bit encoding whose output is a common superstring of every instance and has length at most 2 times the optimum in symbols. This is the headline claim. Not rebuilt here.
Sources
- Lean proofLean proof: OAI/Computability/Superstring/Main.leanLean statement: Superstring.lean (comparator challenge)
- CodeOpenAI math release: A Polynomial-Time 2-Approximation for Shortest Common Superstring
- Problem recordTarhio and Ukkonen, A greedy approximation algorithm for constructing shortest common superstrings (1988)