Factor-two shortest common superstring
Status OpenLLM status Open unverified
Top Open Problems unknownunknown Not reported cataloguedOpenOpenStatement
Definitions and mathematical statement
Statement recorded in the supplied source.
Can a deterministic algorithm polynomial in the total encoded length of any finite collection of ordinary strings return a common superstring of length at most twice the minimum?Short English statement
Can a deterministic algorithm polynomial in the total encoded length of any finite collection of ordinary strings return a common superstring of length at most twice the minimum?Sources
- S1 OpenAI, manuscript citation page. Source of the formulation motivating this local problem. https://github.com/openai/math/blob/adc7f1241b42e322a6451854ab7e4b4c146bf78a/preprints/A-Polynomial-Time-2-Approximation-for-Shortest-Common-Superstring-September-24-2026/README.md.
Statement licence: CC-BY-4.0 · Source file
Contributions 1
OpenAI claim summary for CS-161
The result supplies the conclusion in this problem with its displayed hypotheses and quantifiers. The broader statements and applications in the manuscript are kept separate from the particular question above. The supporting result is manuscript 1 (family 128; 2026-09-24).
Factor-two shortest common superstring
OpenAI's claim
OpenAI presents the following claims relevant to this question, with manuscript numbers following paper order in Sources. In manuscript 1 (family 128; 2026-09-24), the asserted result is that ordinary shortest common superstring admits one deterministic polynomial-time factor-two algorithm on fully encoded string lists.Mathematical statement of the claimed result
Manuscript 1.
For any finite explicitly represented collection $\mathcal S$ of ordinary strings, write $\operatorname{OPT}(\mathcal S)$ for the shortest length of a string containing every member as a contiguous substring. The claim supplies a deterministic algorithm, polynomial in total encoded input size, returning a common superstring $T$ with \[ |T|\le2\operatorname{OPT}(\mathcal S). \]Outline of the argument
For manuscript 1 (family 128; 2026-09-24), a balanced graph of occurrences is organized into periodic layers. Maximal rotations and agreement constraints identify unblocked windows; collective incoming and outgoing connection rules link their closed walks while charging at most twice the optimal occurrence budget.Formal verification
For manuscript 1 (family 128; 2026-09-24), OpenAI lists Lean statements for this assertion: ordinary shortest common superstring admits one deterministic polynomial-time factor-two algorithm on fully encoded string lists.The selected statement includes the clause used for this problem.
The linked family Comparator checks are Superstring.lean.
Their named declarations include OAI.Superstring.main.
This site has not executed the Lean code. Described statement coverage is not an independent proof check.
Status caveat
The manuscripts were produced by an internal OpenAI model. OpenAI cautions that results without formalization can contain mistakes. This site has not independently checked the proofs; the label records the scope of OpenAI's claim.Sources
- OpenAI, A Polynomial-Time 2-Approximation for Shortest Common Superstring, 2026-09-24; citation key
OAI:A-Polynomial-Time-2-Approximation-for-Shortest-Common-Superstring-September-24-2026. PDF (GitHub); PDF (direct); Manuscript page and citation; Latest version; Statement source: thm:main. - Family 128: Lean scope.
- Comparator Superstring.json.
- Comparator Superstring.lean.
- OpenAI catalogue entry.