OctoInformBeta

OpenAI preprint, September 2026 · §3. The algorithm and its structural certificate

§3 (setting): compatible states, accepted sets, and Definition 3.2: Compatible splits with bounded Boolean descriptions organize the recursive subproblems

Recursive acceptance and scheduling layers.

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

Let JJ be a job set and r⊆J×Jr\subseteq J\times J a precedence relation, with (x,y)∈r(x,y)\in r meaning that xx must precede yy. A scheduling subproblem concerns an ambient set W⊆JW\subseteq J. The item defines recursive acceptance of these subproblems and the layers of a dynamic program that stores schedule blocks.

A job triple ZZ in JJ is a finite subset with |Z|=3|Z|=3.✦ A schedule block B=(h,t)B=(h,t) on JJ consists of a nonnegative length hh and a time assignment t:J→ℕt:J\to\mathbb N.✦ Write B⌀B_{\varnothing} for the empty schedule block.

Boolean Descriptions

A Boolean structural formula pp over an atom set AA is a positive or negative atom, or a conjunction or disjunction of two formulas.✦ Fix an assignment a↦Ba⊆Ja\mapsto B_a\subseteq J. For formulas pp and qq over AA, the interpretation ⟦p⟧\llbracket p\rrbracket and leaf count ℓ(p)\ell(p) are defined by (1), where complements are taken in JJ: ⟦a⟧=Ba,⟦¬a⟧=J\Ba,ℓ(a)=ℓ(¬a)=1,⟦p∧q⟧=⟦p⟧∩⟦q⟧,⟦p∨q⟧=⟦p⟧∪⟦q⟧,ℓ(p∧q)=ℓ(p∨q)=ℓ(p)+ℓ(q).\begin{aligned} \llbracket a\rrbracket&=B_a, &\llbracket\neg a\rrbracket&=J\setminus B_a, &\ell(a)&=\ell(\neg a)=1,\\ \llbracket p\land q\rrbracket &=\llbracket p\rrbracket\cap\llbracket q\rrbracket, &\llbracket p\lor q\rrbracket &=\llbracket p\rrbracket\cup\llbracket q\rrbracket, &\ell(p\land q)&=\ell(p\lor q)=\ell(p)+\ell(q). \end{aligned}(1)

A job set W⊆JW\subseteq J has a bounded Boolean description with leaf allowance kk, written 𝖣k(W)\mathsf D_k(W), when it satisfies (2): 𝖣k(W)⇔there is a formula p with ⟦p⟧=W and ℓ(p)≤k.\mathsf D_k(W)\quad\Longleftrightarrow\quad \text{there is a formula }p\text{ with } \llbracket p\rrbracket=W\text{ and }\ell(p)\le k.(2)✦ A relative Boolean description FF of a set L⊆JL\subseteq J inside W⊆JW\subseteq J, with leaf allowance kk, is a globally described subset of JJ whose intersection with WW is LL; write 𝖱kW(L)\mathsf R_k^W(L) for its existence in (3): 𝖱kW(L)⇔there is F⊆J with 𝖣k(F) and L=W∩F.\mathsf R_k^W(L)\quad\Longleftrightarrow\quad \text{there is }F\subseteq J\text{ with } \mathsf D_k(F)\text{ and }L=W\cap F.(3) The fixed allowance for structural acceptance is K=10000K=10000.

The Definition

Definition 1. Fix the precedence relation rr and the atom assignment. A structural split vertex u=(L,Z,R)u=(L,Z,R) of WW, with ZZ a job triple, is a partition satisfying (4); write 𝒱(W)\mathscr V(W) for the set of these vertices: u∈𝒱(W)⇔W=L∪̇Z∪̇R∧r∩((Z×Z)∪(Z×L)∪(R×L)∪(R×Z))=⌀∧𝖱KW(L)∧𝖱KW(R).\begin{aligned} u\in\mathscr V(W)\quad\Longleftrightarrow\quad &W=L\mathbin{\dot\cup}Z\mathbin{\dot\cup}R\\ &{}\land r\cap\bigl((Z\times Z)\cup(Z\times L) \cup(R\times L)\cup(R\times Z)\bigr)=\varnothing\\ &{}\land\mathsf R_K^W(L)\land\mathsf R_K^W(R). \end{aligned}(4)✦

An admissible split transition u→𝒫vu\xrightarrow{\mathcal P}v relative to a property 𝒫\mathcal P of job sets is an ordered pair of vertices u=(L,Z,R)u=(L,Z,R) and v=(L′,Z′,R′)v=(L',Z',R') in 𝒱(W)\mathscr V(W) satisfying (5): u→𝒫v⇔L∪Z⊆L′∧𝒫(L′\(L∪Z)).u\xrightarrow{\mathcal P}v\quad\Longleftrightarrow\quad L\cup Z\subseteq L' \quad\land\quad\mathcal P\bigl(L'\setminus(L\cup Z)\bigr).(5)✦ Write u→𝒫,*vu\xrightarrow{\mathcal P,*}v for a finite path of such transitions, including a path of length zero, and write Lu,RuL_u,R_u for the left and right parts of a vertex uu.

A job set WW is structurally accepted at depth dd, written 𝖠d(W)\mathsf A_d(W), when it satisfies (6): 𝖠0(W)⇔𝖣K(W)∧W=⌀,𝖠d+1(W)⇔𝖣K(W)∧[W=⌀∨∃u,v∈𝒱(W):𝖠d(Lu)∧u→𝖠d,*v∧𝖠d(Rv)].\begin{aligned} \mathsf A_0(W)&\quad\Longleftrightarrow\quad \mathsf D_K(W)\land W=\varnothing,\\ \mathsf A_{d+1}(W)&\quad\Longleftrightarrow\quad \mathsf D_K(W)\land\Bigl[W=\varnothing\ \lor\\ &\qquad\exists u,v\in\mathscr V(W):\ \mathsf A_d(L_u)\land u\xrightarrow{\mathsf A_d,*}v\land\mathsf A_d(R_v)\Bigr]. \end{aligned}(6)✦

A scheduling state ss on JJ is an ordered triple of finite job sets; write 𝒮(J)\mathscr S(J) for the set of these states, as in (7), where 𝒫fin(J)\mathcal P_{\mathrm{fin}}(J) denotes the collection of finite subsets of JJ.

Equality of scheduling states is decidable. 𝒮(J)=𝒫fin(J)3.\mathscr S(J)=\mathcal P_{\mathrm{fin}}(J)^3.(7)✦

For lists ℱ\mathcal F and 𝒵\mathcal Z of finite job sets, and a list ℋ\mathcal H of pairs consisting of a finite job set and a schedule block, let 𝒯r,ℱ,𝒵(ℋ)\mathcal T_{r,\mathcal F,\mathcal Z}(\mathcal H) denote the table of successful outputs obtained by solving each scheduling subproblem in ℱ\mathcal F using the schedule blocks in ℋ\mathcal H. The scheduling layers ℋk\mathcal H_k are lists of pairs consisting of a finite job set and a schedule block, defined by (8): ℋ0=[(⌀,B⌀)],ℋk+1=𝒯r,ℱ,𝒵(ℋk).\mathcal H_0=[(\varnothing,B_{\varnothing})], \qquad \mathcal H_{k+1}=\mathcal T_{r,\mathcal F,\mathcal Z}(\mathcal H_k).(8)✦

In the paper, the result reads: compatible partitions W=L∪̇Z∪̇RW=L\mathbin{\dot\cup}Z\mathbin{\dot\cup}R have an antichain triple ZZ and a relative description of LL, initial and final states have accepted LL and RR, respectively, a transition requires L∪Z⊆L′L\cup Z\subseteq L' and acceptance of L′\(L∪Z)L'\setminus(L\cup Z), and a bounded-description hierarchy recursively marks at least one actual slot at every nonempty node after permitted interval reordering, takes its nonempty open gaps as children, globally describes each node, and relatively describes the jobs earlier than every mark in original time.

What Is Checked

The structural definitions are stated over a job set JJ with a precedence relation rr and an assignment of job sets to atoms; the scheduling layers additionally take lists of candidate job sets and triples.