Non-monotone Behaviors in MIN/MAX/AVG Circuits and their Relationship to Simple Stochastic Games

摘要: In this paper, 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 polynomialtime algorithm is known, despite significant efforts to find such an algorithm. Our investigation will be concerned with the relative computational power of properties 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 observe that the stable circuit problem is in PLS∩ PPAD and will demonstrate the power of MIN/MAX/AVG circuits when we allow the circuit to signal acceptance by switching the direction of output of a MIN or MAX gate. Specifically, we find that the associated computational problem is PSPACE-hard, so unless NP= PSPACE this variant is harder than the original stable circuit problem.