Department of Computer Science | Institute of Theoretical Computer Science

Theory of Combinatorial Algorithms

Prof. Emo Welzl

We show that the problem of finding optimal strategies for both players in a simple stochastic game reduces to the generalized linear complementarity problem (\GLCP) with a $\P$-matrix, a well-studied problem whose hardness would imply $\NP=\coNP$. This makes the rich \GLCP\ theory and numerous existing algorithms available for simple stochastic games. As a special case, we get a reduction from binary simple stochastic games to the $\P$-matrix linear complementarity problem (\LCP).