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.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
No solutions have been posted yet.