Randomized quasipolynomial-time mean-payoff games
There is a uniform randomized algorithm that computes the complete zero-threshold winning set of a finite mean-payoff game with arbitrary signed integer edge weights encoded in binary, correctly with probability at least , using at most bit operations on every random tape for an absolute constant , where is the total explicit binary input length.
The proof in Section 8 cleanly assembles the preceding results, and each component (correctness probability, termination, and bit complexity) is rigorously established in earlier sections.
“Theorem 1.1. There is a uniform randomized algorithm that, for every such game, returns the entire set U = {v ∈ V : there is a Max strategy σ such that for every Min strategy τ, MPw(πv,σ,τ ) ≥ 0} correctly with probability at least 7/8. For an absolute constant C > 0, on every random tape its total cost is at most 2 C(log2 (L+2))2 bit operations in a standard model polynomially equivalent to a uniform probabilistic Turing machine. The bound includes preprocessing, recursive calls, intermediate arithmetic, and random-bit generation.” · Show in paper