OctoInformBeta

OpenAI preprint, September 2026 · §2. Full schedules, frames, and descriptions

Lemma 2.3: Finite interpretations of Boolean formulas, with a uniform time bound at leaf allowance K=10000K=10000

Bounded descriptions have polynomial enumerations.

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 scheduling algorithm that describes candidate job subsets by Boolean formulas needs a finite list of candidates and a bound on the cost of producing it. The relevant formulas use rank thresholds and cones of precedence around triples of jobs. Their allowance counts leaves, including repeated occurrences of an atom.

Let JJ be a finite job set of size NN, with precedence relation rr. In a padded three-machine scheduling instance, N=3TN=3T for the deadline TT. A job triple Z⊆JZ\subseteq J is a set of three jobs.✦ For a relation RR on JJ and a job triple Z⊆JZ\subseteq J, the predecessor cone PR(Z)P_R(Z), successor cone DR(Z)D_R(Z), and weak cones PRw(Z)P_R^{\mathrm w}(Z) and DRw(Z)D_R^{\mathrm w}(Z) are the subsets of JJ defined in (1). PR(Z)={x∈J:∃z∈Z,R(x,z)},DR(Z)={x∈J:∃z∈Z,R(z,x)},PRw(Z)=PR(Z)∪Z,DRw(Z)=DR(Z)∪Z.\begin{aligned} P_R(Z)&=\{x\in J:\exists z\in Z,\ R(x,z)\},& D_R(Z)&=\{x\in J:\exists z\in Z,\ R(z,x)\},\\ P_R^{\mathrm w}(Z)&=P_R(Z)\cup Z,& D_R^{\mathrm w}(Z)&=D_R(Z)\cup Z. \end{aligned}(1) A scheduling boundary is a left endpoint, a job triple, or a right endpoint.✦ At the left endpoint both predecessor cones are empty and both successor cones are JJ; at the right endpoint these conventions are reversed.

For two rank functions ρ,ρ‾:J→ℕ\rho,\bar\rho:J\to\mathbb N, a working orientation ε∈{0,1}\varepsilon\in\{0,1\} selects the relation and rank in (2). (R0,ρ0)=(r,ρ),R1(x,y)=r(y,x),ρ1=ρ‾.(R_0,\rho_0)=(r,\rho),\qquad R_1(x,y)=r(y,x),\qquad \rho_1=\bar\rho.(2) An atomic structural predicate is a Boolean constant, a rank threshold, or one of the five triple sets in (3), with either working orientation.✦ Its interpretation 𝒜r,ρ,ρ‾\mathcal A_{r,\rho,\bar\rho} assigns the indicated subset of JJ to the atom. ⌀,J,{x∈J:ρε(x)≤k},{x∈J:k≤ρε(x)}(0≤k≤N+1),Z,PRε(Z),DRε(Z),PRεw(Z),DRεw(Z).\begin{gathered} \varnothing,\quad J,\qquad \{x\in J:\rho_\varepsilon(x)\le k\},\quad \{x\in J:k\le\rho_\varepsilon(x)\} \quad(0\le k\le N+1),\\ Z,\quad P_{R_\varepsilon}(Z),\quad D_{R_\varepsilon}(Z),\quad P_{R_\varepsilon}^{\mathrm w}(Z),\quad D_{R_\varepsilon}^{\mathrm w}(Z). \end{gathered}(3)✦ For a job list qq, the triple enumeration lists the sets obtained from ordered choices of three entries of qq, retaining those of cardinality three.✦ The structural alphabet Σ(q)\Sigma(q) lists both constants, all thresholds, and all five cone kinds for every listed triple, in both orientations.✦ Repetitions in these lists are retained. Write qNq_N for the list of job indices 0,…,N−10,\ldots,N-1, and ΣN=Σ(qN)\Sigma_N=\Sigma(q_N).

Formulas and Their Enumeration

A Boolean structural formula pp over an atom set AA is an expression consisting of a signed atom of AA, or a conjunction or disjunction of two Boolean structural formulas over AA.✦ For a Boolean structural formula pp over AA and an assignment 𝒜\mathcal A of subsets of JJ to atoms in AA, the interpretation ⟦p⟧𝒜\llbracket p\rrbracket_{\mathcal A} is a subset of JJ and the leaf count ℓ(p)\ell(p) is an integer, both defined by (4); complements are relative to JJ. ⟦a⟧𝒜=𝒜(a),⟦¬a⟧𝒜=𝒜(a)c,ℓ(a)=ℓ(¬a)=1,⟦p∧q⟧𝒜=⟦p⟧𝒜∩⟦q⟧𝒜,⟦p∨q⟧𝒜=⟦p⟧𝒜∪⟦q⟧𝒜,ℓ(p∧q)=ℓ(p∨q)=ℓ(p)+ℓ(q).\begin{aligned} \llbracket a\rrbracket_{\mathcal A}&=\mathcal A(a),& \llbracket\neg a\rrbracket_{\mathcal A}&=\mathcal A(a)^c,& \ell(a)=\ell(\neg a)&=1,\\ \llbracket p\wedge q\rrbracket_{\mathcal A} &=\llbracket p\rrbracket_{\mathcal A}\cap\llbracket q\rrbracket_{\mathcal A},& \llbracket p\vee q\rrbracket_{\mathcal A} &=\llbracket p\rrbracket_{\mathcal A}\cup\llbracket q\rrbracket_{\mathcal A},& \ell(p\wedge q)=\ell(p\vee q)&=\ell(p)+\ell(q). \end{aligned}(4) A set FF has a description with leaf allowance kk under 𝒜\mathcal A when it belongs to the collection 𝒟k(𝒜)\mathcal D_k(\mathcal A) in (5). 𝒟k(𝒜)={⟦p⟧𝒜:ℓ(p)≤k}.\mathcal D_k(\mathcal A)= \{\llbracket p\rrbracket_{\mathcal A}:\ell(p)\le k\}.(5)✦ The finite interpretation ⟦p⟧𝒜fin\llbracket p\rrbracket^{\mathrm{fin}}_{\mathcal A} of a Boolean structural formula pp under an assignment 𝒜\mathcal A is the finite job set obtained by performing the operations of (4) on finite job sets.✦

For an alphabet list Σ\Sigma of atoms in AA, the bounded-depth enumeration ℬd(Σ)\mathcal B_d(\Sigma) is a list of Boolean structural formulas over AA, defined recursively; at depth zero it is empty. At depth d+1d+1 it lists both signs of every entry of Σ\Sigma, followed by both binary connectives applied to every ordered pair from ℬd(Σ)\mathcal B_d(\Sigma). Write [k]={0,…,k−1}[k]=\{0,\ldots,k-1\}. The template list 𝒯k\mathcal T_k is the sublist in (6), with [k][k] enumerated in increasing order. 𝒯k=[s∈ℬk([k]):ℓ(s)≤k].\mathcal T_k=[s\in\mathcal B_k([k]):\ell(s)\le k].(6)✦ The assignment list 𝒰Σ,k\mathcal U_{\Sigma,k} lists every function f:[k]→Af:[k]\to A obtained by choosing an entry of Σ\Sigma at each index, retaining repetitions.✦ For a template s∈𝒯ks\in\mathcal T_k and an assignment f:[k]→Af:[k]\to A, the substituted formula s[f]s[f] is the formula obtained by replacing each index ii in ss by f(i)f(i) without changing signs or connectives.✦

The formula family ℱΣ,𝒜,k\mathcal F_{\Sigma,\mathcal A,k} and the effective structural family ℰr,ρ,ρ‾,q,k\mathcal E_{r,\rho,\bar\rho,q,k} are the lists in (7), ordered first by assignment and then by template. ℱΣ,𝒜,k=[⟦s[f]⟧𝒜:f∈𝒰Σ,k,s∈𝒯k],ℰr,ρ,ρ‾,q,k=[⟦s[f]⟧𝒜r,ρ,ρ‾fin:f∈𝒰Σ(q),k,s∈𝒯k].\begin{aligned} \mathcal F_{\Sigma,\mathcal A,k} &=\bigl[\llbracket s[f]\rrbracket_{\mathcal A}: f\in\mathcal U_{\Sigma,k},\ s\in\mathcal T_k\bigr],\\ \mathcal E_{r,\rho,\bar\rho,q,k} &=\bigl[\llbracket s[f]\rrbracket^{\mathrm{fin}}_{ \mathcal A_{r,\rho,\bar\rho}}: f\in\mathcal U_{\Sigma(q),k},\ s\in\mathcal T_k\bigr]. \end{aligned}(7) Here finite atomic interpretation selects from JJ exactly the jobs satisfying the atom.✦

The Uniform Implementation

A Boolean adjacency matrix MM on NN jobs is a function M:{0,…,N−1}2→{0,1}M:\{0,\ldots,N-1\}^2\to\{0,1\}✦; its relation rMr_M satisfies rM(x,y)r_M(x,y) exactly when M(x,y)=1M(x,y)=1.✦ For a key function hh on the job indices with values in a linearly ordered set, the rank function ρh\rho_h orders jobs by hh according to (8). The canonical key pairs a job’s predecessor count with its index, ordered lexicographically.✦ ρh(x)=1+|{y:h(y)<h(x)}|,cM(x)=|{y:rM(y,x)}|,hM(x)=(cM(x),x),ρM=ρhM,ρ‾M(x)=N+1−ρM(x).\begin{aligned} \rho_h(x)&=1+|\{y:h(y)<h(x)\}|,& c_M(x)&=|\{y:r_M(y,x)\}|,\\ h_M(x)&=(c_M(x),x),& \rho_M&=\rho_{h_M},\qquad \bar\rho_M(x)=N+1-\rho_M(x). \end{aligned}(8)

A binary tree is empty or an ordered pair of binary trees.✦ A tree encoding of a set of values assigns a binary tree to each value.✦ For fixed tree encodings of its input and output values, an implementation of a function ff is a finite register program that, on the encoding of each input xx, returns the encoding of f(x)f(x) within a specified charge.✦ Execution starts with all other registers empty and ends with the input preserved, the result in a distinct output register, and all remaining registers empty. The serialization size of a binary tree is one for the empty tree and one plus the two subtree sizes for a pair.✦ Primitive instructions charge one plus the sizes of the values read or overwritten; sequencing and control tests each charge one. An implementation of a family of functions is uniform when one finite register program and one charge function apply at every index, sending each encoded input to the encoded value of the corresponding function.✦ The binary serialization of a tree is the word consisting of a zero for an empty tree, or a one followed by the serializations of the first and second subtrees for a pair.✦

The compiled atomic set enumeration returns the finite interpretations of ΣN\Sigma_N under rM,ρM,ρ‾Mr_M,\rho_M,\bar\rho_M.✦ Compiled assignment enumeration lists the assignments 𝒰Σ,k\mathcal U_{\Sigma,k}✦, and compiled template evaluation returns the finite interpretations of a supplied template list under a supplied assignment.✦ The compiled structural family enumeration is a uniform implementation returning ℰrM,ρM,ρ‾M,qN,k\mathcal E_{r_M,\rho_M,\bar\rho_M,q_N,k} from the list qNq_N of all job indices and MM.✦ Denote its running time charge by tk(N,M)t_k(N,M), and fix K=10000K=10000 for the cost bound. The compiled predecessor count routine takes the universe listing, a Boolean adjacency matrix MM, and a job xx, and returns the number of jobs preceding xx under rMr_M.✦ The compiled predecessor count vector routine takes the universe listing and MM and returns the function assigning each job its predecessor count under rMr_M.✦ For a supplied count function cc and job xx, the compiled count based ranking routine uses the universe listing to return one plus the number of jobs with smaller count, or equal count and smaller index.✦ The compiled job ranking routine takes the universe listing and MM and returns the canonical job rank function ρM\rho_M.✦ The compiled rank reversal routine takes the universe listing and a rank function ρ\rho and returns the function x↦N+1−ρ(x)x\mapsto N+1-\rho(x).✦ The compiled forward or reverse ranking routine takes the universe listing and MM and returns ρM\rho_M in the original orientation and ρ‾M\bar\rho_M in the reversed orientation.✦ For a supplied rank function ρ\rho, the compiled rank threshold set routine uses the universe listing to enumerate either all sets {x:ρ(x)≤k}\{x:\rho(x)\le k\} or all sets {x:k≤ρ(x)}\{x:k\le\rho(x)\}, for k=0,…,N+1k=0,\ldots,N+1.✦ The compiled rank threshold enumeration takes the universe listing and MM and lists the lower threshold sets followed by the upper threshold sets for every k=0,…,N+1k=0,\ldots,N+1, using ρM\rho_M in the original orientation and ρ‾M\bar\rho_M in the reversed orientation.✦ For a chosen orientation and a list of cone kinds, the compiled cone enumeration takes the universe listing and MM and lists the corresponding finite cone sets for every enumerated job triple, ordered first by cone kind and then by triple.✦

The Claim

Theorem 1 (Lemma 2.3). For an alphabet list Σ\Sigma containing every atom and any set interpretation 𝒜\mathcal A of those atoms, membership has the characterization (9) for every allowance kk and job set FF. F∈ℱΣ,𝒜,k⇔F∈𝒟k(𝒜).F\in\mathcal F_{\Sigma,\mathcal A,k} \quad\Longleftrightarrow\quad F\in\mathcal D_k(\mathcal A).(9)✦ For any alphabet list, the list length is given by (10), counting repetitions. |ℱΣ,𝒜,k|=|Σ|k|𝒯k|.|\mathcal F_{\Sigma,\mathcal A,k}|=|\Sigma|^k\,|\mathcal T_k|.(10)✦ The structural alphabet on all NN job indices satisfies (11). |ΣN|≤20(N+2)3.|\Sigma_N|\le 20(N+2)^3.(11)✦ Let rr be a decidable relation on finite JJ, let ρ,ρ‾\rho,\bar\rho be rank functions, and let qq contain every job. For a set FF with a description of at most kk leaves under 𝒜r,ρ,ρ‾\mathcal A_{r,\rho,\bar\rho}, its finite job set FfinF_{\mathrm{fin}} satisfies (12). Ffin∈ℰr,ρ,ρ‾,q,k.F_{\mathrm{fin}}\in\mathcal E_{r,\rho,\bar\rho,q,k}.(12)✦ For every job list qq, the effective family has the length in (13). |ℰr,ρ,ρ‾,q,k|=|Σ(q)|k|𝒯k|.|\mathcal E_{r,\rho,\bar\rho,q,k}|=|\Sigma(q)|^k\,|\mathcal T_k|.(13)✦ At allowance K=10000K=10000, a constant C∈ℕC\in\mathbb N independent of NN and MM gives the uniform bound (14) for every NN and Boolean adjacency matrix MM. t10000(N,M)≤C(N+2)90010.t_{10000}(N,M)\le C(N+2)^{90010}.(14)✦

In the paper, the result reads: the family can be generated deterministically in polynomial time and represented by NN-bit vectors.

What Is Checked

The set enumeration statements concern alphabet lists and finite job universes with supplied relations and rank functions; their completeness assertions require the relevant lists to contain every atom or every job. The running time statement concerns the uniform compiled program on a universe listing and an arbitrary Boolean adjacency matrix, with the canonical ranks of (8).