OctoInformBeta

OpenAI preprint, September 2026 · §1. Introduction · §1

§1 (setting): ordinary strings, explicit encoding and unrestricted optimum: Ordinary words, unrestricted superstrings and polynomial time measured in input bits

Symbol length and encoded input length.

Hover over a blue or green term in the text, or a node in the graph, to find it in the other. Select it to read its declaration both in Lean and in words.

The Setting

Shortest common superstring is an optimization problem on finite words. Its objective uses a symbol count, while running time uses the bit length of the explicitly represented input.

List Delimiters

Write ϵ\epsilon for an empty sequence and ‖\Vert for concatenation, and represent bits by 00 and 11. For a map ee taking elements to bit strings, write aAaA for a list with first element aa and remaining list AA; the prefix marker list encoding EeE_e is the bit string defined recursively by (1): Ee(ϵ)=1,Ee(aA)=0‖e(a)‖Ee(A).E_e(\epsilon)=1, \qquad E_e(aA)=0\Vert e(a)\Vert E_e(A).(1)✦

The Definition

Definition 1. An ordinary symbol σ\sigma is a finite bit string, with symbol alphabet Σ\Sigma given by (2): Σ={0,1}*.\Sigma=\{0,1\}^{*}.(2)✦ A word ww over the alphabet Σ\Sigma is a finite sequence of symbols from Σ\Sigma; the set of words 𝒲\mathcal W is (3): 𝒲=Σ*.\mathcal W=\Sigma^{*}.(3)✦ An instance SS is a finite list (s1,…,sm)(s_1,\ldots,s_m) of words, belonging to the instance set ℐ\mathcal I in (4): ℐ=𝒲*.\mathcal I=\mathcal W^{*}.(4)✦

The symbol encoding EΣE_\Sigma is the function from ordinary symbols to bit strings that applies the list encoding (1) with the one-bit encoding b↦(b)b\mapsto(b), as specified in (5): EΣ(σ)=Eb↦(b)(σ).E_\Sigma(\sigma)=E_{b\mapsto(b)}(\sigma).(5)✦ The word encoding E𝒲E_{\mathcal W} is the function from words to bit strings that encodes each word’s list of symbols according to (6): E𝒲(w)=EEΣ(w).E_{\mathcal W}(w)=E_{E_\Sigma}(w).(6)✦ For an instance SS, its instance encoding Eℐ(S)E_{\mathcal I}(S) is the bit string in (7): Eℐ(S)=EE𝒲(S).E_{\mathcal I}(S)=E_{E_{\mathcal W}}(S).(7)✦ Write |w||w| for the symbol length of a word, L(S)=∑i=1m|si|L(S)=\sum_{i=1}^{m}|s_i| for the total input symbol length, and N(S)=|Eℐ(S)|bitN(S)=|E_{\mathcal I}(S)|_{\mathrm{bit}} for the encoded input bit length.

A common superstring TT of an instance SS is a word containing every input word as a contiguous substring, as in (8); empty factors are permitted: CS⁡(S,T)⇔∀s∈S∃u,v∈𝒲,T=u‖s‖v.\operatorname{CS}(S,T) \quad\Longleftrightarrow\quad \forall s\in S\;\exists u,v\in\mathcal W,\quad T=u\Vert s\Vert v.(8)✦ The unrestricted optimum OPT⁡(S)\operatorname{OPT}(S) is the minimum symbol length of a common superstring among all words in 𝒲\mathcal W, as in (9): OPT⁡(S)=min⁡{|T|:T∈𝒲,CS⁡(S,T)}.\operatorname{OPT}(S) =\min\bigl\{|T|:T\in\mathcal W,\ \operatorname{CS}(S,T)\bigr\}.(9)✦

A function f:ℐ→𝒲f:\mathcal I\to\mathcal W has a polynomial-time implementation if a deterministic stack machine with a finite alphabet for each stack computes Eℐ(S)↦E𝒲(f(S))E_{\mathcal I}(S)\mapsto E_{\mathcal W}(f(S)) in time polynomial in N(S)N(S).✦ Here 𝒯fin\mathcal T_{\mathrm{fin}} denotes these machines: Poly⁡(f)⇔∃M∈𝒯finM computes Eℐ(S)↦E𝒲(f(S))in time polynomial in N(S).\operatorname{Poly}(f) \quad\Longleftrightarrow\quad \exists M\in\mathcal T_{\mathrm{fin}}\; \begin{gathered} M\text{ computes }E_{\mathcal I}(S)\longmapsto E_{\mathcal W}(f(S))\\ \text{in time polynomial in }N(S). \end{gathered}(10)✦

What Is Checked

The definitions are stated over the words and instances in (3) and (4), and over deterministic stack machines with a finite alphabet for each stack in (10).