OctoInformBeta

OpenAI preprint, September 2026 · §1. Introduction

Theorem 1.1: Optimal schedules and exact deadline decisions for nonempty acyclic instances of unit-length jobs

Polynomial time for three-machine scheduling.

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

Three identical machines can execute at most three unit-length jobs in each time slot. Precedence constraints require a job to finish before any of its successors starts. The optimization problem asks for the smallest number of slots; a deadline request asks whether a prescribed number suffices.

A precedence instance GG on nn jobs is an explicitly listed directed graph with job set V={0,…,n−1}V=\{0,\ldots,n-1\} and edge list EE.✦ The edge relation of a precedence instance with edge list EE is the relation that holds between two jobs exactly when their ordered pair belongs to the list. A precedence instance is acyclic when no job has a nonempty directed path back to itself.✦ A feasible schedule τ\tau for GG with deadline TT is a map V→ℕV\to\mathbb N satisfying 1≤τ(v)≤T,|{v∈V:τ(v)=t}|≤3,(u,v)∈E⇒τ(u)<τ(v).1\le\tau(v)\le T,\qquad |\{v\in V:\tau(v)=t\}|\le3,\qquad (u,v)\in E\ \Longrightarrow\ \tau(u)<\tau(v).(1)✦ The conditions in (1) apply to every job, time slot and listed edge, respectively.

A request x=(n,G,d)x=(n,G,d) consists of an instance and either a nonnegative integer deadline d=Td=T or the symbol d=⋆d=\star, which requests optimization.✦ A binary answer oo is a correct output for the instance GG and request dd, written 𝒞(G,d,o)\mathcal C(G,d,o), when it has the following meaning: for d=⋆d=\star, it gives the slot list (τ(0),…,τ(n−1))(\tau(0),\ldots,\tau(n-1)) of a feasible schedule whose deadline is minimum among all feasible schedules; for d=Td=T, it gives a schedule satisfying (1), or reports infeasibility exactly when no such schedule exists.✦

The Scheduling Procedure

The reachability relation rr used by the scheduling procedure is the relation obtained from the edge list by nn reachability extensions.✦ With R0R_0 the set of listed edges, these extensions are Rj+1=Rj∪{(u,v):∃z∈V,(u,z)∈Rjand(z,v)∈R0},r=Rn.R_{j+1}=R_j\cup \{(u,v):\exists z\in V,\ (u,z)\in R_j\ \text{and}\ (z,v)\in R_0\}, \qquad r=R_n.(2) For a deadline TT with n≤3Tn\le3T, the padded job set is J={0,…,N−1}J=\{0,\ldots,N-1\}, where N=3TN=3T; the padded relation retains rr on the original jobs and leaves all added jobs isolated.✦ The deadline solver applies the full scheduling solver to this padded relation and restricts a returned time assignment to VV; it returns failure when n>3Tn>3T.✦

A job triple ZZ is a three-element subset of JJ.✦ The canonical rank ρ(x)\rho(x) of a job x∈Jx\in J orders jobs by the lexicographic key consisting of their predecessor count and their numerical label.✦ The reverse rank ρ‾(x)\bar\rho(x) is defined by c(x)=|{y∈J:r(y,x)}|,ρ(x)=1+|{y∈J:(c(y),y)<lex(c(x),x)}|,ρ‾(x)=N+1−ρ(x).c(x)=|\{y\in J:r(y,x)\}|,\qquad \rho(x)=1+|\{y\in J:(c(y),y)<_{\mathrm{lex}}(c(x),x)\}|, \qquad \bar\rho(x)=N+1-\rho(x).(3)✦ The two working frames use r,ρr,\rho and the reversed relation with ρ‾\bar\rho from (3), respectively.

For a boundary triple ZZ, its strict predecessor cone P(Z)P(Z) consists of jobs preceding some member of ZZ, and its strict successor cone D(Z)D(Z) consists of jobs following some member of ZZ. The weak predecessor and successor cones Pw(Z)P^{\mathrm w}(Z) and Dw(Z)D^{\mathrm w}(Z) of a boundary triple Z⊆JZ\subseteq J are the subsets of JJ obtained by adjoining ZZ to its strict predecessor and successor cones, respectively. A boundary may also be a fictitious left or right endpoint: their predecessor cones are ⌀,J\varnothing,J, respectively, and their successor cones are J,⌀J,\varnothing; the weak cones have those same endpoint values.

For a working frame ε\varepsilon, write ρε\rho_\varepsilon for ρ\rho in the original frame and ρ‾\bar\rho in the reversed frame. An atomic structural set is a constant set ⌀\varnothing or JJ, a rank threshold {x:ρε(x)≤k}\{x:\rho_\varepsilon(x)\le k\} or {x:k≤ρε(x)}\{x:k\le\rho_\varepsilon(x)\} with 0≤k≤N+10\le k\le N+1, or one of Z,P(Z),D(Z),Pw(Z),Dw(Z)Z,P(Z),D(Z),P^{\mathrm w}(Z),D^{\mathrm w}(Z) in either working frame ε\varepsilon. A structural formula is an expression formed from atomic sets or their complements by intersection and union.✦ The size of a structural formula is its number of leaves, counting each occurrence separately.✦ The effective structural family ℱK\mathcal F_K is the list of sets obtained by substituting atomic sets into formula templates with at most KK leaves, where K=10000K=10000; the templates are enumerated up to depth KK, and the atom assignments range over all choices at KK labeled positions.✦

A scheduling state s=(L,Z,R)s=(L,Z,R) on a subset U⊆JU\subseteq J is compatible when its parts partition UU, its middle part ZZ is a triple of mutually incomparable jobs, and no precedence points from ZZ to LL or from RR to L∪ZL\cup Z.✦ The prefix of a scheduling state is the union L∪ZL\cup Z of its left and middle parts. The candidate states are s(U,F,Z)=(U∩F,Z,U\((U∩F)∪Z)),F∈ℱK,s(U,F,Z)=\bigl(U\cap F,\ Z,\ U\setminus((U\cap F)\cup Z)\bigr), \qquad F\in\mathcal F_K,(4)✦ filtered by compatibility, with ZZ ranging over the enumerated job triples.

A schedule block b=(h,t)b=(h,t) on JJ consists of a nonnegative length hh and a time assignment t:J→ℕt:J\to\mathbb N.✦ Concatenating blocks b=(h,t)b=(h,t) and b′=(h′,t′)b'=(h',t') on JJ with first job set U⊆JU\subseteq J adds their lengths and assigns t(x)t(x) on UU, and h+t′(x)h+t'(x) elsewhere.✦ The empty block has length and times zero; the one-slot triple block has length and times one. A state extends a block for its left part by its middle triple and a further block; finishing a state uses this same concatenation.

The subset solver uses a table of previously obtained blocks. Its initial markings attach the table’s block for LL to each compatible state (L,Z,R)(L,Z,R) for which that block is present. A marking can extend to a state whose left part contains the marked state’s prefix, using a table block for the intervening difference.✦ Each expansion retains an existing marking or takes the first successful extension.✦ After NN expansions, the solver takes the first marked state whose right part has a table block and finishes that state; the empty subset receives the empty block.✦ Scheduling layers begin with the empty-subset entry and repeatedly tabulate successful subset solutions for ℱK\mathcal F_K using the preceding layer.✦ The full solver returns the entry for JJ after NN layers.✦

The minimum makespan search tests deadlines 1,…,n1,\ldots,n in increasing order and retains its first success.✦ Write A(G,d)A(G,d) for the procedure’s binary output: the deadline solver supplies the answer when d=Td=T, and the minimum makespan search supplies it when d=⋆d=\star.✦

Binary Requests and Computation

The input word b(x)b(x) starts with 00 for an optimization request or with 11 followed by the encoded deadline for a deadline request, then gives the explicitly listed job labels 1,…,n1,\ldots,n and the edge list with one-based endpoints.✦ A natural number is written as a binary numeral preceded by its length in unary and a zero; each list is prefixed by its length in that same integer format. The input length is L(x)=|b(x)|L(x)=|b(x)|. A failure answer is the single bit 00; a schedule answer begins with 11 and then gives its length-prefixed slot list.✦

A deterministic multitape Turing machine MM has a fixed finite number of tapes and fixed finite state and symbol sets. Its transition reads the current control state and the symbols under the heads, selects a new control state, writes a symbol on each tape and optionally moves each head; an undefined transition halts. The initial configuration has state zero, input on tape zero and all other tapes blank.✦ Successive configurations follow the transition, with a halted configuration retained thereafter.✦ Write time⁡M(b)\operatorname{time}_M(b) for the number of transitions before halting and out⁡M(b)\operatorname{out}_M(b) for the binary word on tape zero from its head to the right, followed by blanks, at that time.

The Claim

Theorem 1 (Uniform polynomial scheduling guarantee). For acyclic precedence instances on at least one job and for optimization requests or deadlines between one and the number of jobs, a fixed deterministic multitape Turing machine MM and a positive integer CC give the following guarantee. Write GG for the instance on n≥1n\ge1 jobs, and let dd be either ⋆\star or a deadline TT with 1≤T≤n1\le T\le n. For the request x=(n,G,d)x=(n,G,d), the machine halts with the guarantee 𝒞(G,d,out⁡M(b(x))),time⁡M(b(x))≤C(L(x)+2)150020.\mathcal C\bigl(G,d,\operatorname{out}_M(b(x))\bigr), \qquad \operatorname{time}_M(b(x))\le C\,(L(x)+2)^{150020}.(5)✦

In the paper, the result reads: for an explicitly listed finite directed acyclic graph specifying precedence constraints on n≥1n\ge1 nonpreemptive unit-length jobs on three identical machines, a uniform deterministic algorithm constructs a feasible schedule of minimum makespan and, given an integer deadline 1≤T≤n1\le T\le n, decides feasibility exactly and returns a schedule on affirmative instances, with both tasks taking O((L+2)150020)O((L+2)^{150020}) deterministic multitape Turing-machine steps, where LL is the total binary input length.

What Is Checked

The guarantee in (5) is stated over explicitly listed acyclic graphs with at least one job, the binary request and answer formats, and the halting output of a single finite multitape machine.

Theorem 2 (Correctness of the scheduling procedure). Let GG be an acyclic precedence instance on n≥1n\ge1 jobs. For every request d∈{⋆}∪ℕd\in\{\star\}\cup\mathbb N, the procedure’s output satisfies (6): 𝒞(G,d,A(G,d)).\mathcal C(G,d,A(G,d)).(6)✦

For the compiled request-answer routine, let u(x)u(x) denote its operation charge on request xx. Its raw time bound is the function B(x)=2000(u(x)+L(x)+|A(G,d)|+1).B(x)=2000\bigl(u(x)+L(x)+|A(G,d)|+1\bigr).(7)✦ A function ff is polynomially bounded of degree ee relative to a size ss when some constant c∈ℕc\in\mathbb N satisfies f(x)≤c(s(x)+2)ef(x)\le c(s(x)+2)^e for every xx.✦

Theorem 3 (Polynomial bound for compiled requests). For requests x=(n,G,d)x=(n,G,d) with an arbitrary finite graph GG and with d=⋆d=\star or d=T≤nd=T\le n, the bound in (8) holds with a single constant C0∈ℕC_0\in\mathbb N. B(x)≤C0(L(x)+2)150020.B(x)\le C_0\,(L(x)+2)^{150020}.(8)✦