Abstract
The complexity of simple stochastic games (SSGs) has been open since they were defined by Condon in 1992. Despite intensive effort, the complexity of this problem is still unresolved. In this paper, building on the results of [4], we establish a connection between the complexity of SSGs and the complexity of an important problem in proof complexity–the proof search problem for low depth Frege systems. We prove that if depth-3 Frege systems are weakly automatizable, then SSGs are solvable in polynomial-time. Moreover we identify a natural combinatorial principle, which is a version of the well-known Graph Ordering Principle (GOP), that we call the integer-valued GOP (IGOP). We prove that if depth-2 Frege plus IGOP is weakly automatizable, then SSG is in P.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Alekhnovich, M., Razborov, A.: Resolution is not automatizable unless w[p] is tractable. In: IEEE Symposium on Foundations of Computer Science (2001)
Andersson, D., Miltersen, P.B.: The complexity of solving stochastic games on graphs. In: Dong, Y., Du, D.-Z., Ibarra, O. (eds.) ISAAC 2009. LNCS, vol. 5878, pp. 112–121. Springer, Heidelberg (2009)
Atserias, A., Bonet, M.: On the automatizability of resolution and related propositional proof systems. Information and Computation 189(2), 182–201 (2004)
Atserias, A., Maneva, E.: Mean-payoff games and propositional proofs. In: Abramsky, S., Gavoille, C., Kirchner, C., Meyer auf der Heide, F., Spirakis, P.G. (eds.) ICALP 2010. LNCS, vol. 6198, pp. 102–113. Springer, Heidelberg (2010)
Bjorklund, H., Vorobyov, S.: Combinatorial structure and randomized subexponential algorithms for infinite games. Theoretical Computer Science 349, 347–360 (2005)
Blum, M., Juba, B., Williams, R.: Non-monotone behaviors in min/max/avg circuits and their relationship to simple stochastic games
Bonet, M., Domingo, C., Gavalda, R., Maciel, A., Pitassi, T.: No feasible interpolation or automatization for AC0-Frege proof systems (1998) (manuscript)
Bonet, M.L., Galesi, N.: optimality of size-width tradeoffs for resolution. Computational Complexity 10, 261–276 (2001)
Bonet, M.L., Pitassi, T., Raz, R.: On interpolation and automatization for frege systems. SIAM J. Comput. 29, 1939–1967 (2000)
Buresh-Oppenheim, J., Morioka, T.: Relativized np search problems and propositional proof systems. In: 19th IEEE Conference on Computational Complexity, CCC (2004)
Chen, X., Deng, X., Teng, S.H.: Settling the complexity of two-player nash equilibria. Journal of the ACM 56 (2009)
Clegg, M., Edmonds, J., Impagliazzo, R.: Using the Gröbner basis algorithm to find proofs of unsatisfiability. In: Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing, Philadelphia, PA, pp. 174–183 (May 1996)
Condon, A.: The complexity of stochastic games. Information and Computation 96, 203–224 (1992)
Condon, A.: On algorithms for simple stochastic games. In: Advances in Computational Complexity Theory. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 13, pp. 51–73 (1993)
Daskalakis, C., Goldberg, P., Papadimtriou, C.H.: The complexity of computing a nash equilibrium. SIAM Journal on Computing 39, 195–259 (2009)
Galesi, N., Lauria, M.: Optimality of size-degree tradeoffs for polynomial calculus. ACM Trans. Comput. Logic 12, 4:1–4:22 (2010)
Gimbert, H., Horn, F.: Simple stochastic games with few random vertices are easy to solve. In: Amadio, R. (ed.) FOSSACS 2008. LNCS, vol. 4962, pp. 5–19. Springer, Heidelberg (2008)
Halman, N.: Simple stochastic games, parity games, mean payoff games and discounted payoff games are all lp-type problems. Algorithmica 49(1), 37–50 (2007)
Huang, L., Pitassi, T.: Automatizability and simple stochastic games (2011), http://www.cs.toronto.edu/~leih/ssg_full.pdf
Krajicek, K., Pudlak, P.: Some consequences of cryptographic conjectures for S 1 2 and EF. In: Leivant, D. (ed.) LCC 1994. LNCS, vol. 960, pp. 210–220. Springer, Heidelberg (1995)
Kumar, V., Tripathi, R.: Algorithmic results in simple stochastic games. Technical Report 855, University of Rochester (2004)
Ludwig, W.: A subexponential randomized algorithm for the simple stochastic game problem. Inf. Comput. 117, 151–155 (1995)
Shapley, L.S.: Stochastic games. Proceedings of the National Academy of Sciences U.S.A. 39, 1095–1100 (1953)
Somla, R.: New algorithms for solving simple stochastic games. Electron. Notes Theor. Comput. Sci. 119(1), 51–65 (2005)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2011 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Huang, L., Pitassi, T. (2011). Automatizability and Simple Stochastic Games. In: Aceto, L., Henzinger, M., Sgall, J. (eds) Automata, Languages and Programming. ICALP 2011. Lecture Notes in Computer Science, vol 6755. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-22006-7_51
Download citation
DOI: https://doi.org/10.1007/978-3-642-22006-7_51
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-22005-0
Online ISBN: 978-3-642-22006-7
eBook Packages: Computer ScienceComputer Science (R0)