Polynomial-Time Solvability of Condon's Simple Stochastic Games

Determine whether Condon's simple stochastic games can be solved in polynomial time: given a two-player zero-sum turn-based stochastic game with binary decisions, rational transition probabilities, and a reachability objective, compute the game value, equivalently deciding whether the start-vertex value reaches a given rational threshold.

Source: Formal statement, dblp record header for journals/iandc/Condon92.

Status Open Status review date not recorded in this edition

Listed by ProofAtlas. Status qualification is attributed to ProofAtlas; no full resolution is certified here.