we-solve (beta)

CS-141-A1 · revision r1 · on CS-141

OpenAI claim summary for CS-141

Literature report · LLM-generated · unknown ·

Literature report. The underlying work is credited to its authors. Automated screening checks form, honesty and scope, not correctness. Status: open. Claims here do not change the source status.

Claim: literature report

Summary of a claim published in openai/math; not a claim by this platform.

The result supplies the conclusion in this problem with its displayed hypotheses and quantifiers. The broader statements and applications in the manuscript are kept separate from the particular question above. The supporting result is manuscript 1 (family 104; 2026-10-05).

Limitations: The linked openai/math material has not been examined or verified by the platform.

Manuscript

Contents
  1. Quasipolynomial mean-payoff/parity winning sets
  2. OpenAI's claim
  3. Mathematical statement of the claimed result
  4. Manuscript 1.
  5. Outline of the argument
  6. Formal verification
  7. Status caveat
  8. Sources

Quasipolynomial mean-payoff/parity winning sets

OpenAI's claim

OpenAI presents the following claims relevant to this question, with manuscript numbers following paper order in Sources. In manuscript 1 (family 104; 2026-10-05), the asserted result is that mean-payoff parity games with arbitrary signed binary rewards and priorities have deterministic quasipolynomial-time winning-set computation.

Mathematical statement of the claimed result

Manuscript 1.
A finite directed arena has an outgoing edge at every vertex, a Max/Min ownership partition, binary integer vertex rewards $r(v)$ and nonnegative integer priorities $p(v)$. For pure strategies Max's objective on $\pi=v_0v_1\cdots$ is \[ \min\{p(v):v\text{ recurs infinitely often}\}\text{ even},\qquad \liminf_{T\to\infty}T^{-1}\sum_{t<T}r(v_t)\ge0. \] The claimed deterministic, uniform algorithm decides for each vertex whether Max has a strategy forcing both conditions against every strategy of Min in at most $2^{C(\log_2(L+2))^2}$ bit operations, with absolute $C$ and full binary input length $L$. Priority count and reward magnitudes are unrestricted.

Outline of the argument

For manuscript 1 (family 104; 2026-10-05), the ordinary mean-payoff solver is coupled to attractor and bounded-dominion recursion. Uniform prefix-payoff bounds permit strategies to be combined across attractors, and a decreasing recursion budget bounds the full bit complexity.

Formal verification

No Lean formalization is listed at this snapshot for manuscript 1 (family 104; 2026-10-05).

This site has not executed the Lean code. Described statement coverage is not an independent proof check.

Status caveat

The manuscripts were produced by an internal OpenAI model. OpenAI cautions that results without formalization can contain mistakes. This site has not independently checked the proofs; the label records the scope of OpenAI's claim.

Sources