OctoInformBeta

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

Proposition 3.1: Valid dynamic programming tables accompany uniform routines with explicit polynomial cost bounds

Recursive acceptance yields full scheduling blocks.

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 three-machine unit-job schedule assigns each job a positive integer slot, puts at most three jobs in a slot, and assigns a smaller slot to every predecessor. Let rr be a precedence relation on a finite job set JJ. A schedule block s=(h,τ)s=(h,\tau) on JJ is a pair consisting of a length h∈ℕh\in\mathbb N and a time assignment τ:J→ℕ\tau:J\to\mathbb N.✦ The family ℬr(W)\mathcal B_r(W) of valid full blocks for W⊆JW\subseteq J is defined by (1): s∈ℬr(W)⇔1≤τ(x)≤h(x∈W),|W|=3h,|{x∈W:τ(x)=t}|≤3(t∈ℕ),τ(x)<τ(y)(x,y∈W,r(x,y)).s\in\mathcal B_r(W)\quad\Longleftrightarrow\quad \begin{gathered} 1\leq\tau(x)\leq h\quad(x\in W),\qquad |W|=3h,\\ |\{x\in W:\tau(x)=t\}|\leq3\quad(t\in\mathbb N),\\ \tau(x)<\tau(y)\quad(x,y\in W,\ r(x,y)). \end{gathered}(1)✦ The empty block has length zero and assigns zero everywhere✦; the single-triple block has length one and assigns one everywhere.✦ Concatenating two blocks adds their lengths, keeps the first assignment on its designated job set, and shifts the second assignment by the first length on all other jobs.✦

Structural Sets and Tables

A job triple ZZ is a subset of JJ of size three.✦ The predecessor and successor cones of a job triple ZZ in JJ are the sets P(Z)={x:∃z∈Z,r(x,z)}P(Z)=\{x:\exists z\in Z,\ r(x,z)\} and D(Z)={x:∃z∈Z,r(z,x)}D(Z)=\{x:\exists z\in Z,\ r(z,x)\}; the weak cones of ZZ include ZZ. A boundary is a triple or either endpoint.✦ The left endpoint has empty predecessor cones and universal successor cones, and the right endpoint has universal predecessor cones and empty successor cones.

For an indexed job set JJ with |J|=N|J|=N, the canonical rank ρ(x)\rho(x) of a job xx is its position when jobs are ordered by predecessor count, breaking ties by job index.✦ The two ranks in (2) describe the original and reversed working frames: p(x)=|{y∈J:r(y,x)}|,ρ(x)=1+|{y∈J:(p(y),y)<lex(p(x),x)}|,ρ‾(x)=N+1−ρ(x),ρ(x)+ρ‾(x)=N+1.\begin{gathered} p(x)=|\{y\in J:r(y,x)\}|,\qquad \rho(x)=1+|\{y\in J:(p(y),y)<_{\mathrm{lex}}(p(x),x)\}|,\\ \bar\rho(x)=N+1-\rho(x),\qquad \rho(x)+\bar\rho(x)=N+1. \end{gathered}(2) In a reversed working frame precedence is reversed as well. Structural atoms are the empty and universal sets, upper and lower rank thresholds with 0≤k<N+20\leq k<N+2, and the five sets Z,P(Z),D(Z),P(Z)∪Z,D(Z)∪ZZ,P(Z),D(Z),P(Z)\cup Z,D(Z)\cup Z in either frame. A Boolean structural formula is an expression formed from signed structural atoms, conjunction and disjunction, interpreted as complementation, intersection and union. The leaf count of a Boolean structural formula is the number obtained by assigning one to each leaf and adding the counts across either binary operation.✦ Fix K=10000K=10000. The structural family ℱ\mathcal F enumerates the sets obtained from all formula templates of depth at most KK and at most KK leaves under all assignments of structural atoms to their KK available labels.✦ A relative description of LL in WW is an expression L=W∩FL=W\cap F with a globally described set FF from the structural family ℱ\mathcal F.

Structural acceptance at depth dd is defined for any family of atomic sets. At every depth the accepted set must have a description with at most KK leaves. At depth zero it must be empty. At depth d+1d+1, a nonempty set must admit a possibly empty chain of compatible scheduling states in which the prefix jobs of each state are contained in the left region of the next, and whose initial left region, terminal right region and intervening gaps are accepted at depth dd.

A scheduling state (L,Z,Q)(L,Z,Q) for WW is compatible when these sets partition WW, ZZ has three jobs with no precedence within it, and precedence never goes from ZZ to LL, from QQ to LL, or from QQ to ZZ.✦ Candidate states have the form in (3), with F∈ℱF\in\mathcal F and ZZ in a supplied list 𝒵\mathcal Z; only compatible candidates are retained: (L,Z,Q)=(W∩F,Z,W\((W∩F)∪Z)),U=L∪Z.(L,Z,Q)=\bigl(W\cap F,\ Z,\ W\setminus((W\cap F)\cup Z)\bigr), \qquad U=L\cup Z.(3) A block table 𝒯\mathcal T is an ordered list of pairs (W,s)(W,s), where WW is a job set and ss is a schedule block.✦ A block table 𝒯\mathcal T is valid, written Good⁡r(𝒯)\operatorname{Good}_r(\mathcal T), when every stored block belongs to ℬr(W)\mathcal B_r(W) for its paired job set WW.✦ Lookup returns the first matching entry✦, and a successful-result table retains just the successful evaluations in their original order.✦ The prefix jobs of a state are its left and middle jobs together, denoted by UU in (3).✦

A marked state is a scheduling state (L,Z,Q)(L,Z,Q) together with a candidate block for its left region LL. Initial markings use lookup in 𝒯\mathcal T. Let u=(Lu,Zu,Qu)u=(L_u,Z_u,Q_u) and v=(Lv,Zv,Qv)v=(L_v,Z_v,Q_v) be scheduling states. A marking at uu can extend to vv when Uu⊆LvU_u\subseteq L_v and the table contains a block for Lv\UuL_v\setminus U_u; the extension concatenates the marked block, the triple of uu, and that gap block.✦ Each marking expansion retains existing markings and otherwise takes the first successful extension.✦ The subset solver Solve⁡r(𝒯,ℱ,𝒵,W)\operatorname{Solve}_r(\mathcal T,\mathcal F,\mathcal Z,W) returns the empty block for empty WW; otherwise, after |J||J| expansions, it takes the first marked state whose right region has a table entry and completes its block through its middle triple and right region.✦ Failure is denoted by ⊥\bot.

The layer table 𝒯0\mathcal T_0 contains only the empty set and empty block. The table 𝒯k+1\mathcal T_{k+1} retains the successful subset-solver results for members of ℱ\mathcal F, using 𝒯k\mathcal T_k. The complete solver FullSolve⁡r\operatorname{FullSolve}_r looks up JJ in 𝒯N\mathcal T_N, using the structural family just defined and the enumeration of all job triples for 𝒵\mathcal Z.✦

Requests and Computation

A precedence instance GG on nn original jobs is an edge list EE.✦ Its reachability relation is obtained from the listed edges by nn repetitions of the operation that retains known pairs and appends one listed edge to each known path.✦ For a deadline TT satisfying n≤3Tn\leq3T, the deadline solver pads to JJ with N=3TN=3T jobs, gives added jobs no precedence links, runs the complete solver on the padded reachability relation, and restricts a returned assignment to the original jobs. It returns failure when n>3Tn>3T. Without a supplied deadline, the makespan search tests positive deadlines in increasing order through nn and retains its first successful answer.✦

A request x=(G,δ)x=(G,\delta) consists of an instance and an optional deadline.✦ Write b(x)b(x) for its input bit string and o(x)o(x) for the algorithm’s output bit string. An integer whose binary word is ww is written 1|w|0w1^{|w|}0w✦, and a list is prefixed by its encoded length.✦ The input begins with a bit recording whether the deadline is present and, when present, its integer representation; it then lists the one-based job labels and the endpoint pairs in EE.✦ The output is a zero bit for failure, or a one bit followed by the list of assigned slots in job index order.✦ The input length and request measure are those in (4), where T0T_0 is the supplied deadline or zero when absent: L(x)=|b(x)|,S(x)=n+|E|+T0+L(x).L(x)=|b(x)|,\qquad S(x)=n+|E|+T_0+L(x).(4)

A tree routine computing a transformation ff with charge cc is a program on finitely many registers holding binary trees, with distinct input and output registers. Its instructions clear, copy or pair register contents, or select a subtree, and combine by sequencing, branching on nonemptiness and looping while a register is nonempty. Starting with xx in the input register and all other registers empty, it terminates at cost at most c(x)c(x) with xx retained in the input register, f(x)f(x) in the output register and every other register empty. The binary serialization of a tree is a zero bit for the empty tree, or a one bit followed by the serializations of its two subtrees in order for a pair. Primitive operation costs include one plus the serialization sizes of the overwritten and read values; sequencing, branching and loop tests also have their specified unit charges. A uniform routine uses one program for every input size.✦ Let cfull(N,M)c_{\mathrm{full}}(N,M) and cans(x)c_{\mathrm{ans}}(x) be the charged running times of the compiled complete solver on a Boolean relation matrix MM and of the compiled request-answer routine. For an arbitrary uniform routine ℛ\mathcal R, write cℛ(x)c_{\mathcal R}(x) for its charge.✦ Polynomial bounds here have one multiplicative constant for all inputs. Define the raw request bound by (5): B(x)=2000(cans(x)+L(x)+|o(x)|+1).B(x)=2000\bigl(c_{\mathrm{ans}}(x)+L(x)+|o(x)|+1\bigr).(5)✦

For a deterministic multitape Turing machine MM, the notation M(b)↓=oM(b)\mathbin{\downarrow}=o means that the machine halts with oo at and to the right of the head on tape zero, followed by blanks; tM(b)t_M(b) denotes that halting time.✦ Initially tape zero contains bb and every other tape is blank.✦

The Claim

Theorem 1. Let JJ be finite and rr a precedence relation. For any atom family and any set WW structurally accepted at depth dd, ℬr(W)≠⌀.\mathcal B_r(W)\ne\varnothing.(6)✦ Given a valid table 𝒯\mathcal T, arbitrary lists ℱ,𝒵\mathcal F,\mathcal Z, and a successful result s=Solve⁡r(𝒯,ℱ,𝒵,W)s=\operatorname{Solve}_r(\mathcal T,\mathcal F,\mathcal Z,W), s∈ℬr(W).s\in\mathcal B_r(W).(7)✦ For arbitrary lists ℱ,𝒵\mathcal F,\mathcal Z and every layer index kk, Good⁡r(𝒯k).\operatorname{Good}_r(\mathcal T_k).(8)✦ For an indexed job set JJ and any successful result s=FullSolve⁡rs=\operatorname{FullSolve}_r, s∈ℬr(J).s\in\mathcal B_r(J).(9)✦ The compiled routine charges satisfy (10) for every Boolean relation matrix MM on NN jobs and (11) for every request xx: cfull(N,M)=O((N+2)150010).c_{\mathrm{full}}(N,M)=O\bigl((N+2)^{150010}\bigr).(10)✦ cans(x)=O((S(x)+2)150011).c_{\mathrm{ans}}(x)=O\bigl((S(x)+2)^{150011}\bigr).(11)✦ For every uniform routine ℛ\mathcal R computing o(x)o(x), there is a single deterministic multitape Turing machine MℛM_{\mathcal R} with fixed finite tape, state and symbol sets such that (12) holds for every request xx: Mℛ(b(x))↓=o(x),tMℛ(b(x))≤2000(cℛ(x)+L(x)+|o(x)|+1).\begin{gathered} M_{\mathcal R}(b(x))\mathbin{\downarrow}=o(x),\\ t_{M_{\mathcal R}}(b(x)) \leq2000\bigl(c_{\mathcal R}(x)+L(x)+|o(x)|+1\bigr). \end{gathered}(12)✦ For requests with T0≤nT_0\leq n, the bound in (5) satisfies (13): B(x)=O((L(x)+2)150020).B(x)=O\bigl((L(x)+2)^{150020}\bigr).(13)✦

In the paper, the result reads: the specified algorithm is uniform, deterministic and polynomial-time, returns a full schedule for every accepted set, and, with K=10000K=10000, decides deadline feasibility and constructs schedules in O((L+2)150020)O((L+2)^{150020}) deterministic multitape steps.

What Is Checked

The scheduling assertions concern finite relations and the full-block conditions in (1); the computational assertions concern the request measure in (4), charged execution of uniform tree programs, and halting output on tape zero. The compiled complete solver returns the result of FullSolve⁡r\operatorname{FullSolve}_r when rr is the relation specified by its Boolean input matrix, and the compiled request routine returns o(x)o(x) for every request xx, using one program for all input sizes in each case.