OctoInform Beta

OpenAI preprint, September 2026 · §7. Bit complexity · §7

Theorem 7.1 [Bit complexity]: With polynomial postprocessing, the compiled solver halts within T≤2C(log⁡2(L+2))2T\le 2^{C(\log_2(L+2))^2} steps on every game code of length LL and every random tape

A quasipolynomial step bound for the randomized solver.

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 mean-payoff game on a graph with vertex set VV of size nn and integer edge weights ww reaches an algorithm as a binary code dd of length LL. The randomized algorithm treated here replaces each weight ww by (n+1)w+1(n+1)w+1, lets WW be the larger of 11 and the largest absolute value of the new weights, and sets B*=8nWB_*=8nW. It works on solver inputs (a,b;B,α,β,k,m)(a,b;B,\alpha,\beta,k,m): a box with corners a≤ba\le b in ℤV\mathbb{Z}^V and reference width B≥b−aB\ge b-a, positive rational support weights α,β\alpha,\beta and budgets k,mk,m. Its recursion draws uniform random indices below a power of two ss and repeats calls in independent trials, whose answers it combines by coordinatewise medians and by majority votes.

The question is its bit complexity: on a machine that reads dd and a tape of random bits, how many steps can a run take, on the worst input of length LL and the worst tape? The library writes the algorithm as a register program, a program on a fixed number of registers holding bit strings that reads random bits as it runs, and bounds the steps of the machine compiled from it.

Register Programs and Machines

A configuration of a register program PP is a pair of a control point of PP and the contents of its registers; the configuration is halted when the control has stopped. The initial configuration init⁡P(x)\operatorname{init}_P(x) of a register program PP on an input bit string xx is the configuration in which PP starts its run on xx.

A random tree is a finite binary tree whose inner nodes are fair coin flips and whose leaves carry values. The expectation 𝔼tf\mathbb{E}_t f of a function ff of the leaves of a random tree tt averages the two subtrees at every flip, and the depth of tt is the largest number of flips on a branch. The random computation tree 𝒯n(P,c)\mathcal{T}_n(P,c) of PP from a configuration cc is the random tree that branches on the random bits PP reads and has at its leaves the configurations PP reaches from cc within nn steps. A random tree tt traces the run of PP from cc when, for every infinite bit sequence and every position in it, following tt along the bits from that position leads to the configuration that PP reaches from cc in as many steps as tt has read bits.✦

The machine MPM_P compiled from a register program PP runs on the input code xGx_G of a mean-payoff game GG with a finite random tape. For an input xx and a number nn, NP(x,n)N_P(x,n) is the step bound of MPM_P for nn steps of PP on xx.

The Solver Program

The solver program PsolP_{\mathrm{sol}} is a register program on five registers, compiled from a flowchart of twelve nodes. On an input dd it runs the preprocessing program, which loads dd and runs the preparation routine; it then draws one fresh fair bit for each unit of the counter the preprocessing leaves, A(d)A(d) bits in all; it runs the postprocessing program, which applies the postprocessing routine to these bits and writes out the digits of its output; and it stops.

The preparation exponent of dd is E(d)=25000⌈log⁡2(L+2)⌉2E(d)=25000\lceil\log_2(L+2)\rceil^2.✦ The preparation routine parses dd as a game and computes nn, B*B_* and the parameters of the recursion: gg, the binary length of B*B_* plus 11; log⁡2s=⌈log⁡2(217(g+1))⌉\log_2 s=\lceil\log_2(2^{17}(g+1))\rceil; the number of trials J=2(s(n+1))6+1J=2(s(n+1))^6+1; the step budget 128ns128ns of the basic solver, the routine that answers on boxes of width at most 128s128s; and the initial support weights αi=βi=1\alpha_i=\beta_i=1 at every vertex ii and budgets k=m=nk=m=n. It writes out 2E(d)2^{E(d)} in unary by repeated doubling and returns the preparation value of dd: a counter of A(d)=2E(d)log⁡2sA(d)=2^{E(d)}\log_2 s units and the auxiliary output aux⁡(d)\operatorname{aux}(d), made of the chunk length log⁡2s\log_2 s, the sample bound ss, the number 2E(d)2^{E(d)} of chunks, the top width B*B_* and the initial accumulator of the stack machine below.✦

An input of the postprocessing routine is a pair z=(ρ,x)z=(\rho,x) of a bit string and auxiliary data, and the solver applies it to (ρ,aux⁡(d))(\rho,\operatorname{aux}(d)).✦ It cuts ρ\rho into 2E(d)2^{E(d)} chunks of log⁡2s\log_2 s bits, each read as a binary number below ss: a chunk sampling state holds the chunk length, the bound ss, the indices drawn so far and the bits not yet used, and the chunk step reads the next chunk and records its index. It then runs a stack machine, which keeps an environment and a state, one step per index. The answer ans⁡(d,ρ)\operatorname{ans}(d,\rho) marks, for each entry qiq_i of the vector qq the machine returns, whether qiq_i exceeds half of B*B_*.✦

Its environment and state together form its accumulator.✦ The environment holds the arena, the game graph with the weights (n+1)w+1(n+1)w+1, and the numbers log⁡2s\log_2 s, ss, JJ and 128ns128ns.✦ The state is a current cell over a stack of pending cells✦; a cell is a tag and a register pack, which holds support weights and budgets, a box, a counter, two vectors, a list of vectors, an orientation and a list of orientations. An orientation is a choice, YY or ZZ, with a list of masks, each marking a set of vertices.✦ A step reads a random index and dispatches on the tag of the current cell: tags 00 to 99 run the jobs solve, ask, trials, update, centers, orient, orientation trials, orientation plus, tighten and reweight, and any other tag hands the current pack back to the pending cell on top of the stack. The initial state calls solve on the initial support weights and budgets and the box [0,B*]V[0,B_*]^V.✦

The solve job returns a prescribed vector when the budget is small, and the output of the basic solver when the box has width B≤128sB\le 128s. Otherwise it tightens the box, orients it, asks once for each mask of the orientation with the budget reweighted by that mask, solves the box capped high, for YY, or low, for ZZ, by B−δB-\delta, where δ=B/(4s)\delta=B/(4s) is the grid width, and caps the result by the coordinatewise minimum, for YY, or maximum, for ZZ, with the answers to these asks. The ask job returns the coordinatewise median, in the box, of JJ trials of solve, which the trials job runs in turn. The tighten job asks with the budget reduced in kk; if the answer moves the floor of the box, its lower corner, at the scale δ\delta, it tightens the box with its floor moved to the answer, and otherwise it asks with the budget reduced in mm and does the same with the ceiling, its upper corner, returning the box when neither moves.

The orientation plus job returns the majority of JJ orientations from orient, run in turn by the orientation trials job: YY when more than half of them choose YY, with all their masks. On a box of width B≤128sB\le 128s, orient takes the basic solver’s vector vv and the mask M={i:B≤2(vi−ai)}M=\{i : B\le 2(v_i-a_i)\}, and returns YY with the complement of MM when MM has measure above one half, the measure of a set of vertices being the one taken with respect to the support weights and budgets, and ZZ with MM otherwise.✦ On a wider box the centers job builds centers u0,…,usu_0,\dots,u_s, with u0u_0 the midpoint μ\mu of the box and uj+1u_{j+1} the update of uju_j: the average, clipped to the box, of the answers to two asks on the box of width B/(32s)B/(32s) centered at uju_j, the first with the budget reduced in kk and the second in mm. If the positive displacement set {i:s(us,i−μi)>2B}\{i : s(u_{s,i}-\mu_i)>2B\} has measure above one half, orient returns YY with its complement; else, if the negative displacement set {i:s(us,i−μi)<−2B}\{i : s(u_{s,i}-\mu_i)<-2B\} does, it returns ZZ with its complement; else it orients the box of width B/8B/8 centered at uιu_\iota, for ι\iota the random index of the step, and adds both sets to the masks of the result.

Step Counts

Write ∥x∥\|x\| for the code size of a datum xx. The preprocessing cost of an input dd is cpre(d)=2L+6∥d∥+cfeed(d)+cprep(d)+10c_{\mathrm{pre}}(d)=2L+6\|d\|+c_{\mathrm{feed}}(d)+c_{\mathrm{prep}}(d)+10, where cfeed(d)c_{\mathrm{feed}}(d) is the cost of feeding the bits of dd and cprep(d)c_{\mathrm{prep}}(d) the step limit of the preparation routine on dd.✦ The postprocessing cost cpost(z)c_{\mathrm{post}}(z) of an input zz of the postprocessing routine is its step limit on zz, plus the cost of emitting the bits of its output, plus 22.✦ For natural numbers KK and ee, the postprocessing budget of dd is cK,e(d)=K(4A(d)+∥aux⁡(d)∥+3)ec_{K,e}(d)=K\bigl(4A(d)+\|\operatorname{aux}(d)\|+3\bigr)^e✦, and the step limit of dd is ℓK,e(d)=cpre(d)+36A(d)+cK,e(d)+20.\ell_{K,e}(d)=c_{\mathrm{pre}}(d)+36\,A(d)+c_{K,e}(d)+20.(1)✦

The total of dd is twice the step bound of the compiled solver program within this limit, TK,e(d)=2NPsol(d,ℓK,e(d)),T_{K,e}(d)=2\,N_{P_{\mathrm{sol}}}\bigl(d,\ell_{K,e}(d)\bigr),(2)✦ and the preparation resource r(d)r(d) of an input dd is r(d)=∥d∥+2E(d).r(d)=\|d\|+2^{E(d)}.(3)

The Claim

Theorem 1 (Bit complexity). Let KK and ee be natural numbers, and for an input dd let LL be its length.

If the postprocessing cost satisfies cpost(z)≤K(∥z∥+1)ec_{\mathrm{post}}(z)\le K(\|z\|+1)^e for every input zz of the postprocessing routine, then for every input dd every leaf of 𝒯ℓK,e(d)(Psol,init⁡Psol(d)) is halted,\text{every leaf of }\mathcal{T}_{\ell_{K,e}(d)}\bigl(P_{\mathrm{sol}}, \operatorname{init}_{P_{\mathrm{sol}}}(d)\bigr)\text{ is halted},(4)✦ and there is a random tree tt that traces the run of PsolP_{\mathrm{sol}} from init⁡Psol(d)\operatorname{init}_{P_{\mathrm{sol}}}(d), has only halted leaves and depth at most ℓK,e(d)\ell_{K,e}(d), and gives, for every function ff from configurations to the rationals, 𝔼tf=2−A(d)∑ρ∈{0,1}A(d)f(hd,ρ),\mathbb{E}_t f=2^{-A(d)}\sum_{\rho\in\{0,1\}^{A(d)}} f(h_{d,\rho}),(5)✦ where hd,ρh_{d,\rho} is the halted configuration whose output is ans⁡(d,ρ)\operatorname{ans}(d,\rho) and whose working registers are empty.

For every register program PP, every mean-payoff game GG with input code xGx_G and every nn, if every leaf of 𝒯n(P,init⁡P(xG))\mathcal{T}_n\bigl(P,\operatorname{init}_P(x_G)\bigr) is halted, then for every random tape ω\omega of 2NP(xG,n)2N_P(x_G,n) bits MP run on G for 2NP(xG,n) steps with tape ω is halted.M_P\text{ run on }G\text{ for }2N_P(x_G,n)\text{ steps with tape }\omega\text{ is halted}.(6)✦

For every input dd, with ℓ=ℓK,e(d)\ell=\ell_{K,e}(d), TK,e(d)=2(3L+8+ℓ(4(L+ℓ)+16)).T_{K,e}(d)=2\bigl(3L+8+\ell\,(4(L+\ell)+16)\bigr).(7)✦

There is a polynomial pp with ℓK,e(d)≤p(r(d))for every input d,\ell_{K,e}(d)\le p\bigl(r(d)\bigr)\quad\text{for every input } d,(8)✦ and a polynomial p′p' with TK,e(d)≤p′(r(d))for every input d.T_{K,e}(d)\le p'\bigl(r(d)\bigr)\quad\text{for every input } d.(9)✦

For every input dd, r(d)+1≤225003⌈log⁡2(L+2)⌉2.r(d)+1\le 2^{25003\lceil\log_2(L+2)\rceil^2}.(10)✦

If a function ff from inputs to natural numbers satisfies f(d)≤q(r(d))f(d)\le q(r(d)) for a polynomial qq and every input dd, there is a natural number CC with f(d)≤2C⌈log⁡2(L+2)⌉2for every input d.f(d)\le 2^{C\lceil\log_2(L+2)\rceil^2}\quad\text{for every input } d.(11)✦ If a function ff from inputs to natural numbers satisfies (11) for a natural number CC, there is a real D>0D>0 with f(d)≤2D(log⁡2(L+2))2for every input d.f(d)\le 2^{D(\log_2(L+2))^2}\quad\text{for every input } d.(12)✦

There is a real C>0C>0 with TK,e(d)≤2C(log⁡2(L+2))2for every input d.T_{K,e}(d)\le 2^{C(\log_2(L+2))^2}\quad\text{for every input } d.(13)✦

In the paper, the result reads: the algorithm has a uniform implementation in a standard bit-operation model such that, for every input of bit length LL and every random tape, the running time, including preprocessing, every recursive execution, intermediate arithmetic and random-bit generation, is at most 2C(log⁡2(L+2))22^{C(\log_2(L+2))^2} for an absolute constant C>0C>0.

The implementation in the box is the machine compiled from the solver program: when cpost(z)≤K(∥z∥+1)ec_{\mathrm{post}}(z)\le K(\|z\|+1)^e for every zz, it has halted after TK,e(d)T_{K,e}(d) steps on the code dd of a game and every random tape, and the constant CC of (13) depends on KK and ee.

What Is Checked

The claim is stated over the solver program, with its preprocessing, its fair bits and its postprocessing stack machine, and over its step limit ℓK,e\ell_{K,e}, its total TK,eT_{K,e} and the preparation resource rr; its halting parts are stated over random computation trees, the random trees that trace a run and the machine compiled from a register program, under the bound on the postprocessing cost.

Of the loops the solver runs, the library proves two size bounds: from a chunk sampling state σ\sigma, the chunk step run over the first jj units of a counter γ\gamma gives a state of code size at most 5(∥(σ,γ)∥+1)25(\|(\sigma,\gamma)\|+1)^2✦, and from an accumulator σ\sigma, the stack machine run over the first jj indices of a list γ\gamma gives an accumulator of code size at most 240(∥(σ,γ)∥+1)122^{40}(\|(\sigma,\gamma)\|+1)^{12}.✦ A third such bound holds for the coordinatewise maximum or minimum of a vector xx with a list of vectors y1,…,yry_1,\dots,y_r, computed as a left fold over the list: for every kk the fold over the first kk vectors has code size at most 20(S+1)220(S+1)^2, where SS is the code size of (x,(y1,…,yr))(x,(y_1,\dots,y_r)).