On the hardness of simple stochastic games

摘要: We examine the problem of finding optimal strategies in simple stochastic games, and the equivalent problem of finding stable configurations of MIN/MAX/AVG circuits. The problem can be seen as a nontrivial extension to linear programming, but no polynomial-time algorithm is known, despite significant efforts to find such an algorithm. Our investigation will be concerned with the relative computational power of certain variants of these circuits. We will begin by defining the computational problems associated with these games and circuits, and stating in which senses the two are equivalent. We will show that restrictions of the problem are in P, that the simple stochastic game problem is in NP∩ coNP, that the stable circuit problem is in PLS∩ PPAD, and that the problem of deciding whether a MIN or MAX gate in a MIN/MAX/AVG circuit will take the left or right input is PSPACE-hard. We will conclude by discussing how these results fit together.