OctoInformBeta

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

Lemma 2.1: The capacity condition gives an equivalence, with explicit polynomial costs for the padded matrix and solver

Feasible deadlines admit full padded schedules.

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

An instance GG of three-machine unit-job scheduling on nn jobs is a list EE of ordered pairs from V={0,…,n−1}V=\{0,\ldots,n-1\}.✦ Its edge relation is membership in EE✦, and its strict precedence relation ≺\prec is the transitive closure of that relation.✦ A feasible schedule τ:V→ℕ\tau:V\to\mathbb N with deadline T∈ℕT\in\mathbb N is an assignment satisfying (1); write 𝒮(G,T)\mathcal S(G,T) for the set of these assignments. 1≤τ(x)≤T(x∈V),|{x∈V:τ(x)=t}|≤3(t∈ℕ),τ(x)<τ(y)((x,y)∈E).1\le\tau(x)\le T\quad(x\in V),\qquad |\{x\in V:\tau(x)=t\}|\le3\quad(t\in\mathbb N),\qquad \tau(x)<\tau(y)\quad((x,y)\in E).(1)✦

For n≤3Tn\le3T, the padded job set is J={0,…,N−1}J=\{0,\ldots,N-1\}, where N=3TN=3T. Its padded precedence relation ≺J\prec_J retains precisely the original precedences, as in (2); the additional jobs are isolated. u≺Jv⇔u<n,v<n,u≺v(u,v∈J).u\prec_J v \quad\Longleftrightarrow\quad u<n,\quad v<n,\quad u\prec v \qquad(u,v\in J).(2)✦

A layout LL of JJ is a bijection from the jobs to the zero-based positions {0,…,N−1}\{0,\ldots,N-1\}.✦ Its slot assignment is (3); the jobs are read in consecutive triples. A full layout LL of JJ for a relation rr on JJ is a layout whose job count is divisible by three and whose slots satisfy tL(x)<tL(y)t_L(x)<t_L(y) whenever r(x,y)r(x,y).✦ Write ℱ(J,r)\mathcal F(J,r) for the set of full layouts. tL(x)=⌊L(x)3⌋+1.t_L(x)=\left\lfloor\frac{L(x)}3\right\rfloor+1.(3)✦

The Structural Family

The complete solver uses a finite family of job subsets described by precedence cones and rank thresholds. For a relation rr on JJ and a job x∈Jx\in J, the predecessor count cr(x)c_r(x) is the number of jobs in JJ that precede xx under rr.✦ For a relation rr on JJ and a job x∈Jx\in J, the canonical rank ρr(x)\rho_r(x) is the position of xx in the ordering of jobs by the lexicographic key (cr(x),x)(c_r(x),x), as in (4); its reverse rank is ρ‾r(x)\bar\rho_r(x). cr(x)=|{y∈J:r(y,x)}|,ρr(x)=1+|{y∈J:(cr(y),y)<lex(cr(x),x)}|,ρ‾r(x)=N+1−ρr(x).\begin{aligned} c_r(x)&=|\{y\in J:r(y,x)\}|,\\ \rho_r(x)&=1+|\{y\in J:(c_r(y),y)<_{\mathrm{lex}}(c_r(x),x)\}|,\\ \bar\rho_r(x)&=N+1-\rho_r(x). \end{aligned}(4)

A job triple ZZ is a subset of JJ with cardinality three.✦ For a job triple ZZ in JJ and a relation rr on JJ, the strict predecessor and successor cones Pr(Z)P_r(Z) and Dr(Z)D_r(Z) are the sets in (5); the weak cones Pr≤(Z)P_r^{\le}(Z) and Dr≤(Z)D_r^{\le}(Z) include ZZ itself. Pr(Z)={x∈J:∃z∈Z,r(x,z)},Dr(Z)={x∈J:∃z∈Z,r(z,x)},Pr≤(Z)=Pr(Z)∪Z,Dr≤(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^{\le}(Z)&=P_r(Z)\cup Z,& D_r^{\le}(Z)&=D_r(Z)\cup Z. \end{aligned}(5)

A frame on JJ consists of a relation on JJ and a rank function ρ\rho. In a frame with rank function ρ\rho, an atomic structural set is ⌀\varnothing or JJ, a rank threshold set {x:ρ(x)≤k}\{x:\rho(x)\le k\} or {x:k≤ρ(x)}\{x:k\le\rho(x)\} with 0≤k≤N+10\le k\le N+1, or a triple or one of its four cones. Atoms use either the original frame (r,ρr)(r,\rho_r) or the reversed frame (rop,ρ‾r)(r^{\mathrm{op}},\bar\rho_r), where rop(x,y)=r(y,x)r^{\mathrm{op}}(x,y)=r(y,x).

A structural formula is a signed atomic leaf, or the conjunction or disjunction of two structural formulas.✦ The value of a structural formula on JJ is a subset of JJ: a negative leaf takes the complement of its atom, and conjunction and disjunction take intersection and union.✦ The leaf count of a structural formula is one for a leaf and the sum of the two counts at a binary operation.✦ For a natural-number parameter KK, a template is a structural formula with labels in place of atomic sets and with KK labels available. The effective family 𝒜K(r)\mathcal A_K(r) is the list obtained by evaluating these templates with depth and leaf count at most KK, under all assignments of atomic sets to the labels.✦ The parameterized complete solver uses 𝒜K(r)\mathcal A_K(r); its fixed version takes K=10000K=10000. For job subsets L⊆W⊆JL\subseteq W\subseteq J, a relative description of LL in WW is an equality L=W∩FL=W\cap F with F∈𝒜K(r)F\in\mathcal A_K(r).

The Padded Solver

A schedule block b=(ℓb,τb)b=(\ell_b,\tau_b) consists of a length ℓb∈ℕ\ell_b\in\mathbb N and a slot assignment τb:J→ℕ\tau_b:J\to\mathbb N.✦ The empty block is e0=(0,x↦0)e_0=(0,x\mapsto0)✦, and the single-triple block is e3=(1,x↦1)e_3=(1,x\mapsto1).✦ For U⊆JU\subseteq J, block concatenation b*Ucb*_U c is the block in (6). b*Uc=(ℓb+ℓc,x↦{τb(x),x∈U,ℓb+τc(x),x∉U.).b*_U c= \left(\ell_b+\ell_c,\quad x\mapsto \begin{cases} \tau_b(x),&x\in U,\\ \ell_b+\tau_c(x),&x\notin U. \end{cases}\right).(6)✦

A scheduling state s=(Ls,Zs,Rs)s=(L_s,Z_s,R_s) on JJ is an ordered triple of subsets of JJ.✦ A scheduling state s=(Ls,Zs,Rs)s=(L_s,Z_s,R_s) is compatible with W⊆JW\subseteq J when Ls,Zs,RsL_s,Z_s,R_s partition WW, ZsZ_s is a job triple with no internal precedence, and rr contains no pair from ZsZ_s to LsL_s or from RsR_s to Ls∪ZsL_s\cup Z_s.✦ The prefix of a scheduling state s=(Ls,Zs,Rs)s=(L_s,Z_s,R_s) is the job subset Us=Ls∪ZsU_s=L_s\cup Z_s.✦ Candidate states are (W∩F,Z,W\((W∩F)∪Z))(W\cap F,Z,W\setminus((W\cap F)\cup Z)), enumerated over the structural family and the list of job triples, then restricted to compatible states.✦ The triple list is obtained by enumerating ordered triples of jobs and retaining their underlying sets when their cardinality is three.✦ Completing or extending a state with blocks b,cb,c gives the block As(b,c)A_s(b,c) in (7). As(b,c)=(b*Lse3)*Usc.A_s(b,c)=(b*_{L_s}e_3)*_{U_s}c.(7)

A scheduling table on JJ is a list pairing subsets of JJ with schedule blocks on JJ, with lookup returning the first matching entry. Each table construction retains the successful results in enumeration order✦, and every search selects the first successful result.✦ Given a table QQ, initial state markings attach Q(Ls)Q(L_s) to a state ss whenever that entry exists. A marking round keeps existing marks. For an unmarked state vv, it searches the previous round’s marked pairs (u,b)(u,b) with Uu⊆LvU_u\subseteq L_v and an entry c=Q(Lv\Uu)c=Q(L_v\setminus U_u), and attaches Au(b,c)A_u(b,c) when successful.

The subset solver on WW returns e0e_0 when W=⌀W=\varnothing. Otherwise it performs NN marking rounds and completes the first marked pair (s,b)(s,b) whose right set has an entry c=Q(Rs)c=Q(R_s), returning As(b,c)A_s(b,c). The layer table starts with the single entry (⌀,e0)(\varnothing,e_0); each successive layer applies the subset solver to the structural family using the previous layer’s table.✦ The complete solver runs NN layers and looks up JJ, returning a block when an entry exists and failure otherwise.✦

A Boolean matrix MM of dimension nn specifies the relation rM(u,v)r_M(u,v) given by Muv=1M_{uv}=1.✦ For any target dimension mm, its padded matrix Bm(M)B_m(M) retains MuvM_{uv} when u<nu<n and v<nv<n, and has zero in every other entry.✦ The padded solver with deadline TT applies the complete solver to the relation specified by B3T(M)B_{3T}(M).✦

A uniform implementation computes its specified function using one finite-register program on binary trees for every input dimension.✦ Let qmat(n,m,M)q_{\mathrm{mat}}(n,m,M) and qsolve(n,T,M)q_{\mathrm{solve}}(n,T,M) denote the charged running times of the respective uniform implementations. For a running-time function qq on inputs xx, a polynomial growth bound of degree dd in a size parameter ss is a bound q(x)≤C(s(x)+2)dq(x)\le C(s(x)+2)^d for a constant C∈ℕC\in\mathbb N independent of xx.✦

The binary serialization of a tree writes a zero for an empty tree and a one followed by the serializations of the head and tail for a pair.✦ Its serialization size |d||d| is the number of bits in this serialization.✦

A tree register program may leave the store unchanged, clear a register, pair two register values, select a head or tail, or copy a register value. Programs also allow sequencing, branching on whether a register is empty, and looping while a register is nonempty.

The execution cost of a primitive register instruction is one plus the serialization sizes of the overwritten and read values, and leaving the store unchanged costs one. Sequencing adds one to the costs of its two parts, and each branch or loop test costs one.

The Claim

Theorem 1. Let GG be a precedence instance on nn jobs and let T∈ℕT\in\mathbb N. For every feasible schedule τ∈𝒮(G,T)\tau\in\mathcal S(G,T), n≤3T.n\le3T.(8)✦ If n≤3Tn\le3T, take JJ and ≺J\prec_J from (2). Then 𝒮(G,T)≠⌀⇔ℱ(J,≺J)≠⌀.\mathcal S(G,T)\ne\varnothing \quad\Longleftrightarrow\quad \mathcal F(J,\prec_J)\ne\varnothing.(9)✦ There are constants Cmat,Csolve∈ℕC_{\mathrm{mat}},C_{\mathrm{solve}}\in\mathbb N such that, for every dimension nn, every Boolean matrix MM of dimension nn, and every target dimension mm, qmat(n,m,M)≤Cmat(n+m+2)1000,q_{\mathrm{mat}}(n,m,M) \le C_{\mathrm{mat}}(n+m+2)^{1000},(10)✦ and, for every deadline T∈ℕT\in\mathbb N, qsolve(n,T,M)≤Csolve(n+T+2)150010.q_{\mathrm{solve}}(n,T,M) \le C_{\mathrm{solve}}(n+T+2)^{150010}.(11)✦

In the paper, the result reads: the original deadline TT is feasible if and only if the padded set JJ has a full schedule, and the padded instance has polynomial size in the stated input encoding.

What Is Checked

The equivalence (9) is stated over finite edge lists under the capacity condition (8); the cost bounds (10) and (11) range over arbitrary Boolean matrices. The execution cost of a uniform implementation is bounded by its charged running time.