Turn-Based Stochastic Mean-Payoff Games in Deterministic Quasipolynomial Time

1 Introduction

Mean-payoff games ask how two players can control the long-run average reward of an infinite play. In the stochastic version, some transitions are chosen by chance. This combines strategic choice with the possibility of moving between regions having different long-run rewards. The input may describe very small transition probabilities and very large rewards with only a few binary digits, so an algorithm whose cost depends on their magnitudes need not be efficient in the input length.

1.1 The problem and the result

An instance consists of a finite directed multigraph G=(V,E) with V=\{1,\ldots,n\}, n\ge1, and at least one outgoing edge at every vertex. The vertex set is partitioned as

Each edge e has an integer reward w(e). At a vertex of V_{\max}, Max chooses the next edge; at a vertex of V_{\min}, Min chooses it; at a vertex i\in V_{\mathrm{ch}}, the next edge is drawn from a prescribed rational probability distribution p_i on the outgoing edges. Rewards and the numerators and positive denominators of the probabilities are encoded in binary. The graph and all edge data are listed explicitly. Loops, parallel edges, zero probabilities, and unreduced fractions are permitted.

Both players observe the complete finite history, including traversed edges, and may use arbitrary behavioral strategies with private randomness. Chance draws have the prescribed conditional law at the current vertex. A pure positional strategy chooses one outgoing edge at each vertex of its player, independently of the preceding history. For a play \pi=(X_0,e_0,X_1,e_1,\ldots) define

Here \sigma and \tau range over Max’s and Min’s behavioral strategies, respectively. The expectation is taken after the pathwise lower limit. If L is the complete binary input length, the decision problem is to output the set

1.2 Historical context

Shapley introduced stochastic games with positive stopping probabilities and characterized their values by a contraction operator [14]. Gillette considered the undiscounted, long-run average objective [8]; Liggett and Lippman supplied the classical stationary-strategy theorem for perfect-information time-average games [11]. The relation between discounting and long-run optimization is also classical. Blackwell showed in finite dynamic programming that one stationary policy is optimal for every discount factor sufficiently close to one [3]. Rational discounted values provide the corresponding stabilization mechanism for perfect-information stochastic games; see, for example, Gimbert and Zielonka [9, Theorem 3].

The computational problem connects several familiar classes of games. A simple stochastic game is a finite turn-based reachability game in which chance chooses fairly between two successors. Condon placed its threshold problem in \mathrm{NP}\cap\mathrm{coNP} [6], and Ludwig gave a randomized subexponential algorithm [12]. Zwick and Paterson developed pseudopolynomial algorithms for deterministic mean-payoff games and a reduction to simple stochastic games [16]. Andersson and Miltersen later proved polynomial-time Turing equivalences among computing values and optimal strategies in simple stochastic, stochastic mean-payoff, and stochastic discounted-payoff games, with numerical parameters—including the discount factor—given in binary [2, Theorem 1]. Randomized strategy-improvement algorithms have subexponential expected bounds [15]. A different line obtains pseudopolynomial bounds when the number of random positions is fixed [1, 4]. Numerical reward and denominator parameters in such bounds distinguish them from a bound in the complete binary input length. Deterministic quasipolynomial algorithms have also been obtained for simple stochastic games of bounded treewidth [5].

Theorem 1.1 also gives a deterministic quasipolynomial algorithm for deciding whether the reachability value of a simple stochastic game is at least 1/2. Make the target absorbing, with reward +1 on its self-loop, and give every other edge reward -1; any other terminal vertex receives a self-loop of reward -1. For every strategy pair the pathwise mean payoff is 2\one_{\{\text{target is reached}\}}-1. Its expectation is twice the reachability probability minus one, so taking the strategy extrema proves the reduction. The transformation increases the input length by at most a constant factor.

An explicit small discount is only one part of the present algorithm. Andersson and Miltersen already bounded a sufficient discount using determinant coefficients and polynomial sign stabilization [2, Lemma 1]; Gaubert, Grand-Clément, and Katz give sharper bounds on Blackwell optimality thresholds [7]. Hansen, Miltersen, and Zwick proved that strategy iteration is strongly polynomial when the discount factor is fixed [10]. The dependence of their bound on the inverse distance of that factor from one does not yield a polynomial bound in its binary encoding. Here the discount has polynomial bit length, and a recursive comparison algorithm controls the cost of locating its fixed point.

For games without chance vertices, a deterministic quasipolynomial algorithm in the complete binary input length is given in OpenAI [13, Theorem 1.1]. Its simultaneous labeling construction is the direct predecessor of the method used here. We extend that construction to discounted operators, so that chance transitions enter through the same order and translation properties as player choices.

1.3 The proof and its main ideas

The first part of the proof replaces the mean-payoff problem by one discounted fixed point. For 0<u<1, the discounted map takes the maximum, minimum, or chance average of u w(e)+(1-u)t_j over edges e:i\to j. It is a contraction and has a unique fixed point v(u). An explicit integer H, of polynomial binary length, gives a nonzero-value gap of at least 1/H and a discount \lambda for which \|v(\lambda)-\val\|_\infty\le1/(16H). Section 2 proves these estimates by elementary bounds on the rational functions of a fixed positional pair. Its gain and bias then give pathwise guarantees against every behavioral opponent. This establishes the payoff convention used here directly.

Finding the discounted fixed point by ordinary contraction iteration would take a number of steps depending on 1/\lambda, which can be exponential in the input length. The second part of the proof treats any monotone map F:\R^n\to\R^n satisfying

In an integer box, a subsolution is an integer vector y satisfying F_i(y)\ge y_i at coordinates above the lower face; a supersolution satisfies the reverse inequality at coordinates below the upper face. A subsolution close to an upper face requires a plus label there, while a supersolution close to a lower face requires a minus label. The procedure assigns each coordinate a positive mass for each sign. Its guarantee holds simultaneously for all comparison vectors whose coordinates away from the opposite face have total mass at most one.

Section 3 adapts the two-pass pivot and mass-reweighting method of OpenAI [13, Sections 4–5]. The crucial translations have a fixed sign: subsolutions move downward and supersolutions upward. The discounted translation identity preserves their required inequalities, allowing comparison vectors in a large box to be used in smaller recursive boxes. Two pivot passes then arrange a redistribution of the masses that keeps the required comparisons valid. At each recursive call, at most one child leaves both mass vectors unchanged. Every other child increases each product of a coordinate’s two masses by a fixed factor. Starting from uniform masses, only O(\log(n+1)) such choices are possible along a path, even when the coordinate range is exponentially large.

The final part explains why these boundary labels suffice to find the fixed point. After scaling, we place an integer subsolution Y and an integer supersolution Z on opposite sides of it, with Z-Y uniformly small. Neither vector is computed. A label excluding one comparison vector from a boundary strip permits that boundary to move inward while retaining both. Section 4 shrinks the enclosing box in this way, and the value gap converts the final approximation into the exact nonnegative-value set.

The reusable part of the argument is the labeling procedure: its correctness uses monotonicity and the scalar translation identity, and does not inspect the graph or the transition probabilities. The two-sided integer comparison vectors provide the link from that procedure to a discounted game. Quantitative discounting supplies the required accuracy, while the recursion determines the deterministic quasipolynomial running time.

Throughout, vector inequalities, extrema, and integer rounding are coordinatewise, and \one denotes the all-ones vector. The proof uses only exact arithmetic.

2 A quantitative discount reduction

We first reduce the sign of each mean-payoff value to an approximation of one discounted fixed point. The reduction needs two quantitative facts: nonzero values are separated from zero, and a discount of polynomial bit length approximates every value more accurately than this separation. We prove both facts directly, including the identification of the limiting discounted value with the expected pathwise lower average.

The discounted fixed-point method originates in Shapley’s work [14]. Our argument for a single positional pair at all small discounts is a quantitative version of the eventual-optimality principle introduced by Blackwell for finite Markov decision processes [3]; stationary optimality for perfect-information stochastic games with limiting-average payoffs was established by Liggett and Lippman [11]. Quantitative thresholds for small-discount optimality are studied further in [7]. The estimates and the payoff convention needed here are proved below.

Let n=|V|, and define

Here W,Q,A_0,H are positive integers. The denominator in the product defining Q is the positive denominator supplied in the input; the fractions need not be reduced. An empty product is one. The explicit input gives n=O(L) and \log Q,\log W=O(L), because the denominator and reward bits are included in L. Therefore

so \lambda_0 has polynomial bit length.

For 0<u<1, define f_u:\R^V\to\R^V by taking at vertex i the maximum, minimum, or prescribed chance average of

according as i belongs to Max, Min, or Chance. This map is monotone and is a contraction in the maximum norm, with constant 1-u. Indeed, each expression in (2.2) changes by at most (1-u)\|t-t'\|_\infty, and taking an extremum or an average preserves that bound. Its iterates from zero converge, because the successive differences decrease geometrically. Their limit is the unique fixed point, denoted v(u). Since f_u preserves [-W,W]^V,

The proof has an algebraic part and a probabilistic part. Rational functions first give a pair that works for every sufficiently small discount, together with its limiting gain G and first-order term \psi. We then use these two vectors to control individual plays against arbitrary behavioral opponents.

2.1 A positional pair valid for all small discounts

Temporarily fix a pure positional pair: one outgoing edge at each Max and Min vertex. Let P be its row-stochastic transition matrix and let r_i be its expected one-step reward at i. At a chance vertex the transition probabilities of parallel edges are added in P, whereas their possibly different rewards are averaged in r. The pair’s discounted equations are

The matrix I-(1-u)P is invertible for 0<u<1: a vector in its kernel would satisfy \|x\|_\infty\le(1-u)\|x\|_\infty. The corresponding affine contraction preserves [-W,W]^V, so its solution satisfies \|x(u)\|_\infty\le W.

The determinant argument follows the rational-function sign method of Andersson and Miltersen [2, Lemma 1]; we derive all coefficient bounds in the input parameters above. For a polynomial a, write \|a\|_{\mathrm{coef}} for the sum of the absolute values of its coefficients. This norm is subadditive and submultiplicative. Every entry of QP and Qr is an integer. Cramer’s rule therefore gives integer polynomials N_i,D with

Each entry of the matrix defining D has coefficient norm at most 3Q. The replacing column defining N_i is Qu r, whose entries have coefficient norm at most QW. Expanding each determinant over its n! permutations gives

Whether this pair’s chosen edge is optimal at a player vertex i is determined by comparisons with every outgoing edge e:i\to j. Each comparison is the sign of

The numerator has coefficient norm at most (3+W)A_0\le H.

To control these signs, let a be any nonzero integer polynomial with \|a\|_{\mathrm{coef}}\le H. Factoring its lowest power of u gives a(u)=u^\ell(c+u q(u)), where c is a nonzero integer. For 0<u\le1/(2H),

Thus the sign of a(u) throughout this interval is the sign of its lowest nonzero coefficient. This observation applies to both the numerator and denominator in (2.10); the denominator is nonzero there by invertibility. Every edge comparison therefore has a constant sign or vanishes identically on the interval.

Now choose attaining edges in the maximum and minimum defining f_{\lambda_0}(v(\lambda_0)). They give a pure positional pair (\sigma^*,\tau^*), and its linear solution at \lambda_0 equals v(\lambda_0). Since \lambda_0\le1/(2H), all edge inequalities that hold at \lambda_0 continue to hold for every 0<u\le1/(2H). For each such u, the pair’s linear solution is consequently a fixed point of f_u, hence equals v(u). The pair is needed for the proof; the algorithm need not compute it.

2.2 The rational gain and its approximation error

Use the polynomials of the pair just selected. Let \ell be the lowest nonzero degree of D. Boundedness of N_i(u)/D(u) as u\downarrow0 implies that u^\ell also divides each N_i. Define \widehat D=D/u^\ell and \widehat N_i=N_i/u^\ell. Their coefficient norms satisfy (2.9), and \widehat D(0) is a nonzero integer. The quotient is analytic at zero, so it has the expansion (2.4), with

The bound (2.3) gives |G_i|\le W. The displayed denominator has magnitude at most A_0, and its numerator is an integer. Thus G_i\ne0 implies |G_i|\ge1/A_0\ge1/H.

The same coefficient bounds also control the approximation error. The polynomial \widehat N_i-G_i\widehat D has constant coefficient zero and coefficient norm at most (1+W)A_0. For 0<u\le1/(2H), the tail of \widehat D has magnitude at most A_0u\le1/2, so |\widehat D(u)|\ge1/2. It follows that

At u=\lambda_0, this is the error claimed in (2.6).

It remains to identify G_i with the mean-payoff value. The gain controls which transitions can persist, and the coefficient \psi then controls the rewards on those transitions. For a selected player edge e:i\to j, substitution of (2.4) into the discounted equation gives

At a chance vertex, the corresponding identities are

At a Min vertex, the inequality v_i(u)\le u w(e)+(1-u)v_j(u) for an arbitrary outgoing edge first gives G_i\le G_j. If G_i=G_j, subtracting this common constant, dividing by u, and letting u\downarrow0 gives

At a Max vertex, the gain inequality and, when the gains agree, the bias inequality both reverse.

2.3 From one-step inequalities to pathwise payoffs

We use two elementary facts about adapted processes. Fixing a selected strategy will give the gain along a play one-sided conditional drift. The first lemma shows that the gain then becomes constant, so only gain-preserving player moves can persist and the bias inequalities apply. The second lemma shows that the centered contributions at chance vertices have vanishing averages.

3 Simultaneous labeling for discounted monotone maps

We now construct the labels that will permit a box to shrink while retaining the integer comparison vectors around the discounted fixed point. The construction depends only on order and on the response to a common translation. We therefore work in the following abstract setting: n\ge1 and F:\R^n\to\R^n satisfy

All vector inequalities, minima, maxima, and floors in this section are coordinatewise. The algorithm uses F only by evaluating \lfloor F(t)\rfloor at integer vectors t.

The two pivot passes and subsequent mass change adapt the simultaneous labeling construction of [13, Sections 4–5]. Here the operator has the discounted translation rule in Equation (3.1). The proof below establishes the required labeling theorem directly; the signs of the witness translations are what make that adaptation possible.

3.1 Witnesses and the labeling guarantee

An input consists of A\in\Z^n, a width

and positive rational mass vectors a,b\in\mathbb Q_{>0}^n. Write u=A+D\one, P=D/32, and a(S)=\sum_{i\in S}a_i, b(S)=\sum_{i\in S}b_i for S\subseteq\{1,\ldots,n\}. The representation in Equation (3.2) is unique. Its short range of mantissas will later allow small relative decreases in the width.

Every claim belongs to its witness’s support, since 0<P<D. The output must respect all these claims simultaneously, although the algorithm is not given any witness and does not search for one.

The existence of a labeling will already follow from the finite box iteration below. The purpose of the recursive construction is to obtain such labels with the controlled branching and decreasing rank of Lemma 3.5, replacing dependence on the numerical width by dependence on its exponent.

3.2 The recursive procedure

A centered call of even width r at an integer pivot k means the call \cL(k-(r/2)\one,r,a',b') with the indicated masses. All calls use the same map F. In a nonbase call set

The pivot will stay between c-M\one and c+M\one. The two passes use narrow centered boxes to identify some labels directly and arrange the remaining witnesses so that the later mass change preserves their admissibility. The downward pass preserves the plus masses, and the upward pass preserves the minus masses. A final wider centered call supplies the signs used to change both mass vectors.

Procedure \cL(A,D,a,b). Execute the first applicable base case. If neither applies, execute Steps 3–6 in order.

1. 1.

   Mass base case. If a_i b_i>1 for every i, return + at i when b_i>1, and return - otherwise.

2. 2.

   Width base case. If d<12, compute t^* by Equation (3.3). Return + at i when t_i^*>A_i+D/2, and return - otherwise.

3. 3.

   Downward pass. Initialize k=c. Make a centered width-q call at k with masses (a,\frac43 b), and use its labels to update all coordinates simultaneously by

   k_i^{\mathrm{new}}= \begin{cases} \max\{c_i-M,k_i-p\},&\text{if the child labels }i\text{ by }-,\\ k_i,&\text{if the child labels }i\text{ by }+. \end{cases} \tag{3.5}

   Replace k by k^{\mathrm{new}} and repeat until an update leaves the pivot unchanged. Denote this last pivot by k^{\downarrow} and set

   I_- =\{i:k_i^{\downarrow}<c_i-P\}. \tag{3.6}
4. 4.

   Upward pass. Start at k=k^{\downarrow}. Make a centered width-q call at k with masses (\frac43 a,b), and update simultaneously by

   k_i^{\mathrm{new}}= \begin{cases} \min\{c_i+M,k_i+p\},&\text{if the child labels }i\text{ by }+,\\ k_i,&\text{if the child labels }i\text{ by }-. \end{cases} \tag{3.7}

   Replace k by k^{\mathrm{new}} and repeat until an unchanged update. Denote the last pivot by k^f and set

   I_+ =\{i:k_i^f>c_i+P\}. \tag{3.8}
5. 5.

   Provisional labels and new masses. Make a centered width-D/2 call at k^f with masses (a,b). For its output \ell^0, define

   (\bar a_i,\bar b_i)= \begin{cases} (\frac45 a_i,\frac85 b_i),&\ell_i^0=+,\\[1mm] (\frac85 a_i,\frac45 b_i),&\ell_i^0=-. \end{cases} \tag{3.9}
6. 6.

   Continuation and overrides. Call \cL(A,D,\bar a,\bar b). In its output replace the signs on I_- by - and those on I_+\setminus I_- by +. Return this label vector.

Each pass includes the final child call whose update changes nothing. That call will certify a mass inequality at the stopped pivot. All coordinates in one update use the same old pivot and the same child output; there is no order-dependent coordinate update.

The purpose of the passes is the following mass property. For every witness with a claim outside its own override set—I_+ for a plus witness and I_- for a minus witness—the coordinates in its support whose provisional labels match its sign will have total mass greater than 3/4. Here mass means a-mass for a plus witness and b-mass for a minus witness. Its original total mass is at most one, so Step 5 will leave its new total mass below

It will therefore remain a witness for the continuation in the unchanged box. At the same time, every product a_i b_i is multiplied by 32/25. We first use this product growth to prove termination; the subsequent witness analysis proves the stated mass property and hence correctness.

The continuation preserves the width, so width reduction alone does not prove termination. The mass products provide the missing measure. Define

This integer is used only in the proof, not computed by the procedure.

3.3 Translating a witness into a centered box

To analyze the labels, we follow an arbitrary parent witness through the centered calls. Translation places its largest deviation from the pivot at one boundary of the child box; clipping removes coordinates far below that largest deviation. The surviving support will identify the mass forced near the largest deviation when a pivot pass stops.

Fix a nonbase input and a pivot k\in[c-M\one,c+M\one]. For a relevant plus witness y, define its peak and gaps by

For a relevant minus witness z, put

The gaps are nonnegative integers and at least one gap is zero. The following lemma handles both signs, including the inequalities introduced by the discount factor.

3.4 What the two pivot passes enforce

We prove correctness by induction on the rank from Lemma 3.5. For the remainder of this subsection, fix a nonbase call and assume that all its children satisfy Theorem 3.2. Witnesses, supports, and claims refer to the parent input unless stated otherwise.

In each pass, the sign whose masses are unchanged protects its own peak: coordinates close enough to that peak must receive its sign and remain stationary. The opposite sign has its masses multiplied by 4/3. At the final unchanged update, any witness of that sign with a claim outside its override set must consequently have mass greater than 3/4 near its peak. The next two lemmas make these statements precise.

The two passes have now separated the claims into those that can safely receive an override and those whose witnesses have substantial mass near a peak at k^f. The wider provisional call labels all that mass with the witness’s sign. Reducing the masses of that sign then keeps each remaining witness admissible for the continuation. Figure 1 summarizes how the two passes supply the information used in this final step.

3.5 Mass reweighting and completion of the proof

4 From labels to an exact decision

We now apply Theorem 3.2 to a scaled discounted map. The labels need not locate its fixed point directly. Instead, we construct two integer comparison vectors on opposite sides of that point. Their coordinatewise distance is small, so a label excluding one vector from a boundary strip also allows that boundary to move past a smaller strip without excluding either vector. Repeating this operation gives the accuracy required by Theorem 2.1.

4.1 Two nearby integer comparison vectors

Use the integers W,Q,A_0,H of Section 2, and set

Let

Then F(x)=x, the map F is monotone, and

Thus F has the properties used in Section 3. Define the integer vectors

Floors and ceilings are coordinatewise; in particular, a floor of a negative number is taken toward minus infinity. These vectors are used only in the proof. The algorithm will not compute them.

4.2 Shrinking the box

Recall that the permitted widths are D=h2^d with 128\le h\le255 and integers d\ge0. Start with

where d_0 is the least nonnegative integer for which D_0\ge2J. The box [A,A+D\one] contains Y and Z.

While D>K, call \cL(A,D,a,b) with a_i=b_i=1/n for all i. Put u=A+D\one and P=D/32. Within the current box, Y is a subsolution and Z is a supersolution, and their support masses are at most one. Consequently, the labeling guarantee has the following contrapositive form:

For example, Z_i\le A_i+P would be a minus claim and would require a minus label.

Let D' be the next smaller permitted width. More explicitly,

The second case has d\ge1, because the loop condition implies D>K>255. Set \delta=D-D'. In the first case \delta/D=1/h\le1/128; in the second case this ratio is 1/256. Thus

Define

Replace (A,D) by (A',D').

At termination, Y\le x\le Z and the invariant imply A_i\le x_i\le A_i+D. Hence

Theorem 2.1 now gives

Output exactly the indices satisfying

If \val(i)=0, (4.10) puts A_i/S at least -1/(8H), so the index is included. If \val(i)>0, the same conclusion holds. If \val(i)<0, the value gap in Theorem 2.1 gives A_i/S\le-1/H+1/(8H)=-7/(8H), so the index is excluded. This proves exact correctness, including equality at zero.

4.3 Bit complexity and uniformity

It remains to show that the potentially large integer widths do not produce a large recursion tree, and that every local computation has polynomial bit cost. The first point uses the mass-product rank of Section 3; the second uses the explicit binary encoding.

Since every vertex has an outgoing edge and the input is explicit, n,|E|=O(L+1). The binary lengths of the probabilities and rewards give

In particular, all integers in (4.1) and (4.5) have O((L+2)^2) bits, and d_0=O((L+2)^2). Reading the input and forming these integers by ordinary exact arithmetic take polynomial time. Every recursive box lies in its parent, and every outer box lies in the initial box. Thus all box endpoints, pivot coordinates, and integer arguments to F have polynomial binary length.

For an integer vector t, the quantities used to evaluate F_i(t) are

Max and Min take exact extrema. At a chance vertex write the encoded probability as p(e)=c_e/d_e with d_e>0. Its weighted sum can be formed with the common denominator QN and integer numerator

Every d_e divides Q, even when input fractions are not reduced. This formula gives polynomial bit lengths and polynomial bit cost for an evaluation and its coordinatewise floors. Zero probabilities and parallel edges require no special handling.

Consider one outer call, whose initial masses are a_i=b_i=1/n. For a recursive call put

The initial value B_0=B(1/n^2) is O(\log(n+1)); this includes n=1, for which B_0=1. Every recursive edge decreases d+B. Only the provisional-label child can preserve B, and it decreases d by one. Each other child decreases B by at least one and does not increase d. Thus the depth is at most

and any root-to-node path contains at most B_0 edges decreasing B. At each node there is at most one B-preserving child and at most

other children: the two pivot passes account for the first term and the reweighted call for the final one.

A path of length \ell with j edges decreasing B is specified by their j positions and at most s_* choices at each such position; the other child, if present, is unique. The total number of nodes is therefore at most

The distinction between these two kinds of children is essential: the depth may be polynomial in L, but branching choices occur only O(\log(n+1)) times on any path.

All masses can be stored as unreduced positive fractions. An edge that changes masses multiplies each by one of a fixed set of rational constants, and so increases its numerator and denominator lengths by at most a constant. The other edge leaves masses unchanged. Thus the mass lengths are polynomial (indeed O(\log(n+1))), and every comparison, update, and support-independent base test has polynomial bit cost. The algorithm does not compute B; it is used only for this analysis.

Outside its children, a nonbase call performs O(n+1) pivot updates and associated vector operations, all of polynomial bit cost. In a width base case, d<12 gives D\le255\cdot2^{11}, an absolute constant, so the clipped-floor iteration uses at most 1+nD polynomial-cost evaluations. The mass base case is also polynomial. Consequently (4.14) bounds the bit cost of one outer call up to a polynomial factor. Lemma 4.2 bounds the number of outer calls by a polynomial as well.

Finally, all loops, tie rules, integer operations, and recursive calls are specified by finite algorithms independent of the input. A depth-first implementation stores a stack of polynomial depth whose individual records have polynomial length. Scanning such a stack or copying a record on a deterministic Turing machine costs at most a polynomial factor per local operation. The final integer tests (4.11) and the output take polynomial time. Absorbing these factors into (4.14) proves the bound 2^{C(\log_2(L+2))^2} for one absolute constant C. This completes the proof of Theorem 1.1.