OctoInformBeta

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

Lemma 3.3: Certificates have a fixed allowance of K=10000K=10000 Boolean formula leaves at every recursive region

Recursive certificates enter the scheduling table.

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

A recursive split certificate for a job set is a recursive division of that set into regions handled at smaller depths. For dynamic programming on three machines, the completeness question is whether the table at a given depth contains every job set with such a certificate. Let JJ be a finite job set with precedence relation rr, and let AA index an assignment of atomic job sets Sa⊆JS_a\subseteq J.

A Boolean structural formula pp over AA is a signed atomic leaf, or a conjunction or disjunction of two structural formulas.✦ The interpretation ⟦p⟧\llbracket p\rrbracket of a Boolean structural formula pp over AA is a subset of JJ: a positive leaf at aa denotes SaS_a, a negative leaf denotes J\SaJ\setminus S_a, and conjunction and disjunction denote intersection and union.✦ The leaf count ℓ(p)\ell(p) of a Boolean structural formula pp over AA is an integer equal to one for a leaf and to the sum of the two constituent counts for either binary operation.✦ A job set W⊆JW\subseteq J is describable with allowance K=10000K=10000 when it satisfies (1). Desc⁡K(W)⇔∃p(⟦p⟧=W∧ℓ(p)≤K).\operatorname{Desc}_K(W) \quad\Longleftrightarrow\quad \exists p\;\bigl(\llbracket p\rrbracket=W\ \land\ \ell(p)\le K\bigr).(1)✦

For a nonnegative integer dd, structural acceptance 𝒜d(W)\mathcal A_d(W) is a recursive condition on a job set W⊆JW\subseteq J, given by (2). Write V(W)V(W) for the structural split vertices of WW, with L(u)L(u) the left region of a vertex uu and R(v)R(v) the right region of a vertex vv. The relation u⤳d*vu\leadsto_d^*v means that a possibly empty chain of admissible structural split transitions leads from uu to vv, with every intervening gap region accepted at depth dd. 𝒜0(W)⇔Desc⁡K(W)∧W=⌀,𝒜d+1(W)⇔Desc⁡K(W)∧(W=⌀∨∃u,v∈V(W)[𝒜d(L(u))∧u⤳d*v∧𝒜d(R(v))]).\begin{aligned} \mathcal A_0(W) &\Longleftrightarrow \operatorname{Desc}_K(W)\ \land\ W=\varnothing,\\ \mathcal A_{d+1}(W) &\Longleftrightarrow \operatorname{Desc}_K(W)\ \land\ \bigl(W=\varnothing\ \lor\ \exists u,v\in V(W)\; [\mathcal A_d(L(u))\ \land\ u\leadsto_d^*v \ \land\ \mathcal A_d(R(v))]\bigr). \end{aligned}(2)✦

A schedule block BB on JJ is a pair consisting of a nonnegative length and an assigned time t(j)∈ℕt(j)\in\mathbb N for each job j∈Jj\in J.✦ A scheduling table 𝒯\mathcal T is an ordered list of pairs of finite job sets and schedule blocks. Lookup searches from the beginning and returns the block at the first matching job set, with no result when that set is absent.✦ The key set keys⁡(𝒯)\operatorname{keys}(\mathcal T) of a table 𝒯\mathcal T consists of the job sets whose lookup returns a block.✦

A job triple QQ of JJ is a subset of JJ of cardinality three.✦ Fix a list ℱ\mathcal F of candidate job sets and a list 𝒞\mathcal C of triples. The scheduling layer 𝒯0\mathcal T_0 is a table consisting of the empty job set paired with the empty schedule block.✦ Given 𝒯d\mathcal T_d, the layer 𝒯d+1\mathcal T_{d+1} is the table of successful answers obtained by applying the subset solver to every member of ℱ\mathcal F, using rr, the triple list 𝒞\mathcal C, and the blocks stored in 𝒯d\mathcal T_d.✦

The Claim

Theorem 1 (Lemma 3.3). Let kk be a nonnegative integer, and let W⊆JW\subseteq J be structurally accepted at depth kk. Then W∈keys⁡(𝒯k).W\in\operatorname{keys}(\mathcal T_k).(3)✦

In the paper, the result reads: if a feasible job set JJ has a hierarchy with bounded descriptions, the algorithm accepts JJ.

What Is Checked

The assertion (3) is stated over a finite job set with precedence, an assignment of atomic job sets, the candidate family and triple list, and structural acceptance at a nonnegative recursive depth.