Factor two, at last?

0:00The problem

Given a few strings, find the shortest string that contains every one of them as a contiguous piece. This is the shortest common superstring problem. For abab and baa, one shortest answer is ababaa, six letters, because the end of the first string overlaps the start of the second. It is a simple model of reassembling a genome from overlapping fragments, and it is NP-hard, so no fast exact algorithm is expected. The natural heuristic, Greedy, repeatedly merges the two strings with the largest overlap. On a family of three strings built from repeated ab and a letter c, Greedy’s answer approaches twice the optimum. In our check, on 2,800 small random instances, Greedy was never worse than about 1.3 times the optimum. In 1988, Tarhio and Ukkonen conjectured that Greedy is always within a factor of two. Blum, Jiang, Li, Tromp and Yannakakis proved Greedy within a factor of four, gave a different algorithm within three, and showed the problem is MAX SNP-hard, which, with the later PCP theorem, puts some constant factor above one out of reach unless P equals NP. Better factors followed: Sweedyk reached 2.5; Mucha, 2 + 11/23; Englert, Matsakis and Veselý, just under 2.466. An August 2026 preprint by Chukhin, Kulikov, Mihajlin and Smal reports 7/3, and a September preprint by Shibata reports that the Greedy conjecture itself is false, with a worst case of at least 9/4. Whether any polynomial-time algorithm achieves two was open.

1:39The claim

Result 128 is a single OpenAI preprint, 19 pages, dated September 24. It claims a deterministic algorithm that, for every finite family of strings, outputs a common superstring at most twice as long as the shortest one. Its running time is polynomial in the full size of the input written out in bits, including the labels of the symbols, so the alphabet may be huge. The algorithm is new; the guarantee is not claimed for Greedy. The paper does not claim that two is the best possible factor. And the lower bound it compares against cannot certify anything better: for the family of all rotations of a word with p distinct letters, the optimum is 2p − 1, while that bound is only p. That observation is ours, not the paper’s. OpenAI published a Lean formalization of the full theorem: a function with a certificate that a multi-stack Turing machine with finite alphabets computes it in polynomial time on the bit encoding, which always returns a common superstring at most twice the optimum, measured in symbols. It runs to 51 files and about 20,000 lines with its imports, not counting Mathlib. We have not run the Lean check.

2:56How the proof goes

The proof works in a graph whose vertices are all substrings of the inputs, including the empty word. An up edge appends a letter and costs one; a down edge deletes the first letter and costs nothing. Suppose a multiset of these edges is balanced, with as many edges entering as leaving each vertex, and connected, reaching the empty word and every input string. Then an Euler tour from the empty word, writing down each appended letter, spells a common superstring, because the current vertex is always a suffix of what has been written. Its length is the number of up edges. So the task becomes building such an edge set cheaply. The algorithm first computes, for every substring s, a count m of s: a number of occurrences that every common superstring must contain. Each input needs one. A word must occur at least as often as all its one-letter extensions on the left combined, and likewise on the right. And a rule for periodic words, which discounts occurrences fenced in by mismatching letters within some substring of the inputs, records repetition that the extensions miss: for the single input a⁶, extensions alone force one a, but the rule forces six. The sum of the counts over single letters, W, is a lower bound on the optimum. Differences of the counts give multiplicities for up and down edges, forming a balanced base graph with exactly W up edges. In our check, every count stayed at or below the true number of occurrences, in every superstring we tried, over 400,000 comparisons. The base graph costs W but may fall apart into pieces, so the rest of the proof connects every piece to the empty word for at most W more. Split the base graph into closed walks. The letters a walk appends, repeated forever, form a periodic text. Walks with the same text are rearranged, without changing any edge, into layers that each go once around the shortest period p. Each layer gets an extra budget of p, and the budgets add up to exactly W. A round trip from the empty word to a vertex costs its length, so layers with short vertices connect cheaply. For the rest, the periodic rule forces a shortened word to occur on a layer whose text, lined up there, is different, perhaps the same pattern shifted; two differently aligned periodic texts can only agree on a short stretch, so that occurrence gives a meeting point. Some layers attach there using only their own budgets; others send a request to a layer of strictly larger period, which is handled later, together with the receiving layer’s own budget. The links paid only by their sources can form cycles, each block of layers waiting on the next. On each cycle, pick the block whose text has the lexicographically greatest rotation. Its link can be realized with a contact word no longer than q, the period of its target. Drop the target’s own outgoing link and join the target’s layers internally instead; that frees q from the target’s budget, which pays for a round trip from the contact to the empty word. Everything is now connected, the added cost is at most W, and the Euler tour spells a superstring of length at most twice W, so at most twice the optimum. Every step searches only polynomially many candidates: there are at most quadratically many substrings, and no count exceeds the total input length, so the whole algorithm runs in polynomial time. In our check, on the same random instances, the optimum never exceeded twice W, as the theorem requires; we did not implement the connection procedure itself.

6:38Where it stands

The preprint is not peer reviewed and has not been revised. The Lean formalization covers the full theorem, including polynomial running time on a Turing machine; we have not run it. The paper is not among those OSVerify reviewed, and we have seen no expert review. If it holds, shortest common superstring has a polynomial-time factor-two approximation, the factor long conjectured for Greedy, reached by a different algorithm. Whether a polynomial-time algorithm can beat two is still open; some constant factor above one is ruled out unless P equals NP.