OctoInformBeta

OpenAI preprint, September 2026 · §9. Running time in the explicit input model

§9 (proof of Proposition 3.1 and Theorem 1.1): uniform machine accounting: Fixed programs account for parsing and binary input and output in a request bound of degree 150020150020

Uniform compilation gives polynomial scheduling time.

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 precedence instance GG on nn indexed jobs is an edge list EE of ordered job pairs.✦ A scheduling request x=(n,G,δ)x=(n,G,\delta) specifies either a deadline δ=T\delta=T or a search for the minimum makespan when δ\delta is absent.✦ The accounting concerns the complete computation from the request bits to a schedule listed in job order, or a failure answer.

Write b(x)b(x) for the request bit string and L(x)=|b(x)|L(x)=|b(x)|. The self-delimiting encoding ee of an integer kk is a bit string consisting of the binary digits of kk in order from least to most significant, preceded by as many ones as there are digits and a zero separator.✦ The length-prefixed encoding of a list is the self-delimiting encoding of its length followed by the encodings of its elements in list order.✦ The request begins with a deadline flag and, when present, its encoded value; the remaining lists give the one-based vertex labels and edge endpoints.✦ The binary parser reads these lists, takes the vertex count as nn, and subtracts one from each edge endpoint, with subtraction truncated at zero.✦ With δ0=T\delta_0=T for a supplied deadline and δ0=0\delta_0=0 otherwise, the request size is the measure in (1). s(x)=n+|E|+δ0+L(x).s(x)=n+|E|+\delta_0+L(x).(1)✦ A bounded deadline request x=(n,G,δ)x=(n,G,\delta) is a scheduling request with δ0≤n\delta_0\le n, where δ0\delta_0 is the supplied deadline or zero when the deadline is absent.✦ The binary natural-number parser counts the initial ones, discards them and the following separator, and interprets the next equally many bits as a least significant first binary numeral; it returns that value and the unconsumed bits.✦ Given a parser for individual elements, the binary list parser first reads a natural number giving the list length, then parses that many elements and returns them in input order together with the remaining bits.✦ The binary deadline parser consumes the first bit, treating an absent bit as zero; a one causes it to parse a natural number as the deadline, and a zero gives an absent deadline with the remaining bits.✦

Reachability is computed from EE by nn rounds of extension: a round retains current pairs and adds (a,b)(a,b) when a current pair (a,z)(a,z) can be followed by an edge (z,b)(z,b). For a deadline TT, the deadline solver returns failure if n>3Tn>3T; otherwise it pads this relation to a job set JJ of size N=3TN=3T, with the added jobs unrelated to all jobs. It runs the complete solver, a dynamic program on structural subsets of the padded job set, and restricts the returned time assignment to the original jobs. Without a deadline, minimum makespan search retains the first successful answer among deadlines 1,…,n1,\ldots,n.✦ The output string o(x)o(x) is a single zero for failure, or a one followed by the length-prefixed list of self-delimiting schedule times.✦

For arbitrary NN, a Boolean matrix AA on the indexed jobs defines the relation r(a,b)r(a,b) by its true entries.✦ Let uNu_N denote the complete job enumeration. The canonical rank orders jobs lexicographically by predecessor count and index; its reverse rank is specified in (2). p(x)=|{y∈J:r(y,x)}|,ρ(x)=1+|{y∈J:(p(y),y)<lex(p(x),x)}|,ρ‾(x)=N+1−ρ(x).\begin{aligned} p(x)&=|\{y\in J:r(y,x)\}|,\\ \rho(x)&=1+|\{y\in J:(p(y),y)<_{\mathrm{lex}}(p(x),x)\}|,\\ \bar\rho(x)&=N+1-\rho(x). \end{aligned}(2) An atomic structural set SS on JJ is a subset of JJ equal to the empty set or JJ, a lower or upper rank threshold at k∈{0,…,N+1}k\in\{0,\ldots,N+1\}, or one of ZZ, P(Z)P(Z), D(Z)D(Z), P(Z)∪ZP(Z)\cup Z and D(Z)∪ZD(Z)\cup Z for a job triple ZZ. Here |Z|=3|Z|=3, 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 include ZZ. Both working orientations are allowed, reversing the relation and using ρ‾\bar\rho in the reversed orientation. A Boolean structural formula φ\varphi on JJ is an expression built from signed atomic leaves by conjunction and disjunction, interpreted as intersection and union, with a negative leaf interpreted by complementation. The leaf count ℓ\ell of a Boolean structural formula φ\varphi is a nonnegative integer defined recursively as one at a leaf and additively at either connective.✦ For an integer allowance KK, the structural family ℱK\mathcal F_K on JJ is an enumeration of the sets obtained by substituting all assignments of atomic sets into formula templates of depth and leaf count at most KK.✦ The complete solver uses K=10000K=10000.

The job triple enumeration runs over all ordered choices of three jobs from the job list, forms their set and retains it when it has cardinality three, preserving repetitions and enumeration order.✦

A compatible scheduling state (LW,Z,RW)(L_W,Z,R_W) for a job set WW is an ordered partition of WW in which ZZ is an antichain triple and no precedence runs from ZZ to LWL_W, from RWR_W to LWL_W, or from RWR_W to ZZ.✦ Candidate states use the relative description in (3) for F∈ℱKF\in\mathcal F_K. (LW,Z,RW)=(W∩F,Z,W\((W∩F)∪Z)).(L_W,Z,R_W)=\bigl(W\cap F,\ Z,\ W\setminus((W\cap F)\cup Z)\bigr).(3)✦ A schedule block ss for a job set WW is a nonnegative length together with a time assignment to the jobs in WW.✦ The empty block has length and times zero✦; the single triple block has length and times one.✦ For blocks s,ts,t on JJ and a job set U⊆JU\subseteq J, their concatenation has length equal to the sum of their lengths, assigns each job in UU its time from ss, and assigns every other job its time from tt plus the length of ss.✦ A subset schedule table 𝒯\mathcal T on JJ is an ordered list pairing job sets with blocks✦, and a state marking table ℳ\mathcal M on JJ is an ordered list pairing scheduling states with blocks.✦ Lookups select the first matching entry✦; successful result tables retain successful evaluations in order.✦

For a target set WW, the compatible state enumeration forms a candidate state for every pair of a member of the structural family and an enumerated triple, then retains exactly the states compatible with WW.✦

The subset solver marks each state’s left part from the subset table. A marking can advance to another state when its prefix LW∪ZL_W\cup Z lies in that state’s left part and the remaining left jobs have a table entry.✦ Block extension concatenates the marked block, its middle triple, and the block for the remaining jobs.✦ Marking expansion retains existing markings and otherwise selects the first successful extension.✦ After NN expansions, completion appends a block for the right part, taking the first successful result; the empty subset receives the empty block.✦ The initial scheduling layer is the table containing the empty job set paired with the empty block; each next layer applies the subset solver to every member of ℱK\mathcal F_K using the preceding layer as its subset table, retaining successful results in order.✦ The complete solver looks up JJ after NN layers.✦

Programs and Their Charges

A binary tree datum dd is a finite tree formed from an empty tree and ordered pairs.✦ The serialization of a binary tree dd gives the empty tree a zero and a pair a one followed by the two subtree serializations✦; |d||d| denotes its length.✦ A tree program PP on finitely many registers is a program built from instructions that do nothing, clear a register, copy a register, select its head or tail, or construct a pair, combined by sequencing, branching on whether a register is nonempty, and looping while a register is nonempty.✦ Head and tail selection both return the empty tree on empty input. A primitive instruction costs one plus the serialization sizes of the overwritten and read values. Sequencing adds one to the component costs; each branch or loop test costs one. A bounded execution ee of a tree program PP with budget HH is an execution of PP whose cost is at most HH.✦

A certified tree program PP for a transformation ff with charge cc is a tree program that takes input dd in its input register, with all other registers empty, and reaches the store containing dd and f(d)f(d) in distinct input and output registers, with all other registers empty, at cost at most c(d)c(d).✦ A tree data encoding η\eta of a set XX is a map assigning a tree to each value in XX.✦ A certified implementation PP of a function ff is a certified tree program computing ff on tree data encodings.✦ A uniform implementation PP of a family of functions fNf_N indexed by size NN is an implementation using one transformation and charge for every size index.✦

Write ι\iota for the tree encoding of bit strings, tfull(N,uN,A)t_{\mathrm{full}}(N,u_N,A) for the compiled complete solver’s charge, and treq(x)t_{\mathrm{req}}(x) for the compiled request answer’s charge on its encoded input. The compiled request answer extracts the job count, graph and optional deadline from the scheduling request, constructs the complete job enumeration, computes the reachability matrix, applies the matrix scheduling answer and serializes its result.✦ The compiled parameterized scheduling solver takes the allowance KK as a parameter. Its specialization at K=10000K=10000 is the compiled complete solver.✦

The compiled request bound BB is defined by (4). B(x)=2000(treq(x)+L(x)+|o(x)|+1).B(x)=2000\bigl(t_{\mathrm{req}}(x)+L(x)+|o(x)|+1\bigr).(4)✦ For an input measure mm, a polynomial growth bound of degree dd for a function hh means the uniform domination in (5), with a natural constant CC independent of the input. h(x)≤C(m(x)+2)dfor every input x.h(x)\le C\bigl(m(x)+2\bigr)^d\qquad\text{for every input }x.(5)✦

A deterministic multitape Turing machine MM is a machine with finite state and tape alphabets whose transition either halts or gives a new state, a written symbol and an optional head movement on each tape.✦ Its initial configuration has state zero and the input on tape zero, with other tapes blank.✦ Bits zero and one use symbols one and two, leaving symbol zero blank.✦ The run iterates transitions and retains a halted configuration.✦ For a deterministic multitape Turing machine MM, input bit string bb, output bit string oo, and time budget HH, write Produces⁡M(b,o;H)\operatorname{Produces}_M(b,o;H) when some configuration of the run on input bb at time at most HH is halted and the contents to the right of the head on tape zero are oo followed by blanks.✦

The Claim

Theorem 1. There are constants Cf,Cr,CB,CLC_f,C_r,C_B,C_L, independent of the matrix or request, with the following bounds. For every enumerated Boolean matrix input, the compiled complete solver satisfies (6). tfull(N,uN,A)≤Cf(N+2)150010.t_{\mathrm{full}}(N,u_N,A)\le C_f(N+2)^{150010}.(6)✦ For every scheduling request, the compiled request answer satisfies (7). treq(x)≤Cr(s(x)+2)150011.t_{\mathrm{req}}(x)\le C_r\bigl(s(x)+2\bigr)^{150011}.(7)✦ For a bounded deadline request, the size comparison is (8). s(x)≤4L(x).s(x)\le 4L(x).(8)✦ For any certified tree program computing ff with charge cc, there is a fixed multitape Turing machine MM whose production bound for bit strings b,ob,o satisfying f(ι(b))=ι(o)f(\iota(b))=\iota(o) is (9). $$\operatorname{Produces}_M\!left( b,o;2000\bigl(c(\iota(b))+|b|+|o|+1\bigr)\right).$$(9)✦ The compiled request bound satisfies (10) for every request and (11) for every bounded deadline request. B(x)≤CB(s(x)+2)150011.B(x)\le C_B\bigl(s(x)+2\bigr)^{150011}.(10)✦ B(x)≤CL(L(x)+2)150020.B(x)\le C_L\bigl(L(x)+2\bigr)^{150020}.(11)✦

In the paper, the result reads: sequential-scan all-set processing takes OK(N15K+13)O_K(N^{15K+13}) time, and the final O((L+2)150020)O((L+2)^{150020}) allowance, with LL the input bit length, includes preprocessing and all nn deadline trials for optimization.

What Is Checked

The bounds concern uniform implementations on size-indexed Boolean matrices and edge-list requests, together with the bounded execution semantics of finite register programs and the halting output semantics of multitape Turing machines.

Binary increment propagates carry through an initial run of ones; iterating it nn times from the empty string gives the standard binary representation of nn.✦ The binary numeral evaluation also equals the left fold of the update k↦2k+bk\mapsto 2k+b over the reversed digit list, starting at zero, where a digit bb has value zero or one.✦

For every nonnegative integer kk, the tree encoding of kk equals the tree encoding of the list of kk copies of the unique element of a one-element set.✦