Computer Sciences Dept.

The Complexity of Stochastic Games

Anne Condon

We consider the complexity of stochastic games simple games of chance played by two players. We show that the problem of deciding which player has the greatest chance of winning the game is in the class NP  co-NP.

Download this report (PDF)

Return to tech report index

Computer Science | UW Home