OctoInformBeta

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

Theorem 3.4: Node and edge certificates control global descriptions and relative cuts

Full layouts yield recursive structural acceptance.

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

Consider a finite set JJ of unit jobs with precedence relation rr, and put N=|J|N=|J|. Structural completeness concerns recursive decompositions of schedules that fill all three machines at every slot, with a fixed allowance for Boolean formula leaves.

A layout pp of JJ is a bijection to the positions 0,…,N−10,\ldots,N-1, read in consecutive triples.✦ Its time assignment is given by (1). tp(x)=⌊p(x)3⌋+1.t_p(x)=\left\lfloor\frac{p(x)}{3}\right\rfloor+1.(1)✦ A layout respects precedence if r(x,y)r(x,y) implies tp(x)<tp(y)t_p(x)<t_p(y).✦ A full layout pp of JJ is a layout that respects precedence and satisfies 3∣N3\mid N; its deadline is T=N/3T=N/3, so N=3TN=3T.✦

A boundary BB of a layout of JJ is a left endpoint, a right endpoint, or a triple Z⊆JZ\subseteq J with |Z|=3|Z|=3.✦ The endpoints occur at times 00 and T+1T+1.✦ An actual boundary ZZ is at ss when 1≤s≤T1\le s\le T and Z={x:tp(x)=s}Z=\{x:t_p(x)=s\}.✦ For boundary times aa and bb, the open window W=(a,b)W=(a,b) is the subset of JJ in (2). (a,b)={x∈J:a<tp(x)<b}.(a,b)=\{x\in J:a<t_p(x)<b\}.(2)✦

The predecessor and successor cones of an actual boundary ZZ, and their weak versions, are defined by (3). PZ={x:∃z∈Z,r(x,z)},DZ={x:∃z∈Z,r(z,x)},PˆZ=PZ∪Z,DˆZ=DZ∪Z.\begin{aligned} P_Z&=\{x:\exists z\in Z,\ r(x,z)\},& D_Z&=\{x:\exists z\in Z,\ r(z,x)\},\\ \widehat P_Z&=P_Z\cup Z,&\widehat D_Z&=D_Z\cup Z. \end{aligned}(3) At the left endpoint both predecessor cones are empty and both successor cones are JJ; at the right endpoint these choices are reversed. A boundary BB at ss separates a set SS in WW when (4) holds; write this condition as Sep⁡B(W,S;s)\operatorname{Sep}_B(W,S;s). (W\S)∩{x:tp(x)<s}⊆PB,W∩S∩{x:s<tp(x)}⊆DB.(W\setminus S)\cap\{x:t_p(x)<s\}\subseteq P_B, \qquad W\cap S\cap\{x:s<t_p(x)\}\subseteq D_B.(4)✦

Descriptions and Recursive Acceptance

An atomic assignment α\alpha assigns a subset of JJ to each atom in a set AA. A Boolean structural formula φ\varphi over AA is a signed atomic leaf, or a conjunction or disjunction of two such formulas.✦ Its interpretation and leaf count ℓ\ell are given by (5), where ∘\circ is either ∧\land or ∨\lor. ⟦a⟧α=α(a),⟦¬a⟧α=J\α(a),⟦φ∧ψ⟧α=⟦φ⟧α∩⟦ψ⟧α,⟦φ∨ψ⟧α=⟦φ⟧α∪⟦ψ⟧α,ℓ(a)=ℓ(¬a)=1,ℓ(φ∘ψ)=ℓ(φ)+ℓ(ψ).\begin{aligned} \llbracket a\rrbracket_\alpha&=\alpha(a),& \llbracket\neg a\rrbracket_\alpha&=J\setminus\alpha(a),\\ \llbracket\varphi\land\psi\rrbracket_\alpha &=\llbracket\varphi\rrbracket_\alpha\cap\llbracket\psi\rrbracket_\alpha,& \llbracket\varphi\lor\psi\rrbracket_\alpha &=\llbracket\varphi\rrbracket_\alpha\cup\llbracket\psi\rrbracket_\alpha,\\ \ell(a)=\ell(\neg a)&=1,& \ell(\varphi\circ\psi)&=\ell(\varphi)+\ell(\psi). \end{aligned}(5) A global description φ\varphi of S⊆JS\subseteq J with allowance kk is a Boolean structural formula satisfying the conditions in (6); 𝖣k(S)\mathsf D_k(S) denotes its existence. A relative kk-leaf description of a set LL in WW is a representation L=W∩FL=W\cap F for some FF with 𝖣k(F)\mathsf D_k(F). $$\mathsf D_k(S)\quad\Longleftrightarrow\quad \exists\varphi,\quad \llbracket\varphi\rrbracket_\alpha=S\quad\hbox{and}\quad\ell(\varphi)\le k.$$(6)✦

A working frame for (J,r)(J,r) is a choice of either forward precedence rr with rank ρ\rho, or reversed precedence rop(x,y)=r(y,x)r^{\mathrm{op}}(x,y)=r(y,x) with rank ρ‾\bar\rho. Original time always means tpt_p. For ranks numbering one order and its reversal, the convention is ρ(x)+ρ‾(x)=N+1\rho(x)+\bar\rho(x)=N+1. The canonical atomic assignment α*\alpha_* interprets Boolean constants as JJ and ⌀\varnothing; its threshold atoms are {x:ρf(x)≤k}\{x:\rho_f(x)\le k\} and {x:k≤ρf(x)}\{x:k\le\rho_f(x)\}, where 0≤k≤N+10\le k\le N+1 and ρf\rho_f is the rank of the chosen frame. Its remaining atoms are ZZ, PZP_Z, DZD_Z, PˆZ\widehat P_Z and DˆZ\widehat D_Z in either frame.

An assignment α\alpha has atomic support for (r,ρ)(r,\rho) if JJ, ⌀\varnothing, every rank tail {x:k≤ρ(x)}\{x:k\le\rho(x)\}, every boundary cone and every triple have a description with one leaf.✦ Recursive structural acceptance 𝒜d(W)\mathcal A_d(W) for (r,α)(r,\alpha) requires 𝖣K(W)\mathsf D_K(W) at every depth, where K=10000K=10000. At depth zero it also requires W=⌀W=\varnothing. At depth d+1d+1, recursive structural acceptance requires either W=⌀W=\varnothing or a possibly empty chain of allowed structural splits of WW, with the initial left region, final right region and every intervening gap accepted at depth dd.

Global Families and Certificates

An indexed global family ℒ=(I,(Ei)i≥0)\mathcal L=(I,(E_i)_{i\ge0}) consists of a finite set I⊆ℕI\subseteq\mathbb N and sets Ei⊆JE_i\subseteq J.✦ Its union is Q=⋃i∈IEiQ=\bigcup_{i\in I}E_i.✦ For an indexed global family ℒ=(I,(Ei)i≥0)\mathcal L=(I,(E_i)_{i\ge0}) and a job x∈Jx\in J, the membership indices of xx form the set {i∈I:x∈Ei}\{i\in I:x\in E_i\}.✦ The last index λ(x)\lambda(x) of a job x∈Jx\in J in this indexed global family is the maximum of its membership indices, with value zero when this set is empty.✦ List priority for jobs x∈Jx\in J in the indexed global family ℒ\mathcal L is lexicographic order on (λ(x),ρ(x))(\lambda(x),\rho(x)).✦ A global upset UU of (J,r)(J,r) is a subset of JJ closed under successors for rr; a downset HH of (J,r)(J,r) is an upset for ropr^{\mathrm{op}}.✦ An indexed global family ℒ=(I,(Ei)i≥0)\mathcal L=(I,(E_i)_{i\ge0}) has upward-closed entries when every EiE_i with i∈Ii\in I is an upset.✦ An indexed global family ℒ=(I,(Ei)i≥0)\mathcal L=(I,(E_i)_{i\ge0}) has injection entries disjoint in WW when Ei∩Ej∩W=⌀E_i\cap E_j\cap W=\varnothing for distinct i,j∈Ii,j\in I with i,j≥2i,j\ge2.✦

A rank threshold run for ℒ\mathcal L on WW is a family of subsets CiC_i of JJ, rank thresholds kik_i and a distinguished subset S1S_1 of JJ satisfying (7). $$\begin{aligned} E_i&=C_i\cap\{x:k_i\le\rho(x)\} &&(i\in I),\\ \mathsf D_{24}(C_0),\qquad \mathsf D_2(C_i)&\quad(i\in I,\ i\ne0),& C_1&=S_1,\qquad\mathsf D_1(S_1),\\ W\setminus S_1&\subseteq C_0,\\ 0\in I,\ x\in W\cap S_1&\ \Longrightarrow\ 1\in I\ \hbox{and}\ x\in E_1. \end{aligned}$$(7)✦

For a layout pp, an indexed global family ℒ\mathcal L with union QQ, and a boundary AA at time aa, the past boundary invariant is the condition that every x∈Qx\in Q with tp(x)≤at_p(x)\le a lies in PˆA\widehat P_A.✦ A layout qq agrees with pp outside WW when q(x)=p(x)q(x)=p(x) for every x∉Wx\notin W.✦ Exchanging x,yx,y in qq swaps their positions.✦ The forbidden exchange invariant for (p,W,ℒ,ρ,A,a)(p,W,\mathcal L,\rho,A,a) is the condition that swapping the positions of x,yx,y in qq violates precedence whenever qq respects precedence and agrees with pp outside WW, x∈W\DAx\in W\setminus D_A, and y∈Qy\in Q has tq(y)=at_q(y)=a and list priority greater than that of xx.✦ The job exchange of x,y∈Jx,y\in J in a layout qq is the layout obtained by interchanging their positions and leaving every other job in place.

A reverse induction seed for WW at boundary BB and time bb is a downset HH satisfying (8). 𝖣24(H),W\PB⊆H⊆{x:tp(x)<b}.\mathsf D_{24}(H),\qquad W\setminus P_B\subseteq H\subseteq\{x:t_p(x)<b\}.(8)✦ A node certificate for (r,ρ,α,p,W)(r,\rho,\alpha,p,W) is a choice of boundaries A,BA,B at a,ba,b, a rank threshold run and a reverse induction seed at (B,b)(B,b), with pp full and subject to (9). Its entries and S1S_1 are upsets, its injection entries are disjoint in WW, and it satisfies the past and forbidden exchange invariants at (A,a)(A,a) on WW. W=(a,b),|I|≤5,W∩Q⊆PB,W\Q⊆DA,𝖣406(W).W=(a,b),\qquad |I|\le5,\qquad W\cap Q\subseteq P_B,\qquad W\setminus Q\subseteq D_A,\qquad \mathsf D_{406}(W).(9)

An edge certificate for (r,ρ,α,p,W)(r,\rho,\alpha,p,W) is a choice of boundaries B,V,A′,B′B,V,A',B' at b,v,a′,b′b,v,a',b', respectively, for a full layout pp with W=(a,b)W=(a,b) and a≤a′<b′≤v<ba\le a'<b'\le v<b, where B′B' is actual. Its cutoffs S,SfS,S_f, a global cutoff S̃\widetilde S, and a downset H−H_- satisfy (10). 𝖣1(Sf),Sep⁡V(W,Sf;v),Sep⁡A′((a,v),S;a′),Sep⁡B′((a,v),S;b′),W∩S⊆PB∩Sf,𝖣205(S̃),W∩S̃=W∩S,𝖣21(H−),W∩H−=W∩S.\begin{aligned} &\mathsf D_1(S_f),\qquad \operatorname{Sep}_V(W,S_f;v),\\ &\operatorname{Sep}_{A'}((a,v),S;a'),\qquad \operatorname{Sep}_{B'}((a,v),S;b'),\\ &W\cap S\subseteq P_B\cap S_f,\\ &\mathsf D_{205}(\widetilde S),\qquad W\cap\widetilde S=W\cap S,\\ &\mathsf D_{21}(H_-),\qquad W\cap H_-=W\cap S. \end{aligned}(10) Its rank threshold run has upset entries and an upset S1S_1, with injection entries disjoint in WW and W∩Q=W\SW\cap Q=W\setminus S. The past invariant holds at (A′,a′)(A',a'); the forbidden exchange invariant holds there on (a′,b′)(a',b').

The Claim

Theorem 1 (Structural completeness and description bounds).

  1. Let rr be transitive. Suppose ρ,ρ‾:J→ℕ\rho,\bar\rho:J\to\mathbb N are injective, increase strictly along r,ropr,r^{\mathrm{op}}, respectively, and are both less than a common positive bound MM. Suppose α\alpha has atomic support in both frames. For a node certificate on WW and any depth d≥|W|d\ge|W|, the acceptance conclusion is (11). 𝒜d(W).\mathcal A_d(W).(11)✦

  2. For the canonical assignment α*\alpha_*, let rr be transitive and let the forward and reverse ranks be injective, bounded above by NN, and strictly increasing along their respective precedence relations. These ranks may be chosen independently. Acceptance and existence of a full layout satisfy (12). 𝒜N(J)⇔there exists a full layout of J respecting r.\mathcal A_N(J)\quad\Longleftrightarrow\quad \text{there exists a full layout of $J$ respecting $r$}.(12)✦

  3. Suppose α\alpha has atomic support for (r,ρ)(r,\rho). Let Q′Q' be the union of an indexed global family, with 𝖣195(Q′)\mathsf D_{195}(Q'), and let 𝖣205(S̃)\mathsf D_{205}(\widetilde S) hold. For boundaries A′,B,B′,VA',B,B',V and sets W′,SW',S, assume the child decomposition identities (13). W′\S=(Q′∩PB′)\PˆA′,W′∩S=(((DA′∩PB)\DˆB′)\DˆV)∩S̃.\begin{aligned} W'\setminus S&=(Q'\cap P_{B'})\setminus\widehat P_{A'},\\ W'\cap S&=\Bigl(\bigl((D_{A'}\cap P_B)\setminus\widehat D_{B'}\bigr) \setminus\widehat D_V\Bigr)\cap\widetilde S. \end{aligned}(13) The resulting global bound is (14). 𝖣406(W′).\mathsf D_{406}(W').(14)✦

  4. Suppose α\alpha has atomic support for (r,ρ)(r,\rho), and let an edge certificate have target boundary B′B' at b′b'. The target cut admits the relative description in (15). $$\exists F\subseteq J,\qquad \mathsf D_{210}(F)\quad\hbox{and}\quad W\cap F=\{x\in W:t_p(x)<b'\}.$$(15)✦

In the paper, the result reads: every feasible full three-machine schedule has a bounded-description hierarchy whose global node predicates and relative split predicates all have fewer than 500500 leaves.

What Is Checked

The claims are stated over finite job layouts and job sets, with transitive precedence and bounded injective ranks for completeness, and with atomic support and the specified decompositions or certificates for the description bounds.