On the complexity of succinct zero-sum games
Lance Fortnow, Russell Impagliazzo, Valentine Kabanets, and Chris Umans
Abstract
We study the complexity of solving succinct zero-sum games, i.e., the games whose payoff matrix M is given implicitly by a Boolean circuit C such that M(i,j)=C(i,j). We complement the known EXP-hardness of computing the exact value of a succinct zero-sum game by several results on approximating the value.
- We prove that approximating the value of a succinct zero-sum game to within an additive factor is complete for the class promise-S2p, the ``promise'' version of S2p. To the best of our knowledge, it is the first natural problem shown complete for this class.
- We describe a ZPPNP algorithm for constructing approximately optimal strategies, and hence for approximating the value, of a given succinct zero-sum game. As a corollary, we obtain, in a uniform fashion, several complexity-theoretic results, e.g., a ZPPNP algorithm for learning circuits for SAT by Bshouty et al. and a recent result by Cai that S2p⊆ZPPNP.
- We observe that approximating the value of a succinct zero-sum game to within a multiplicative factor is in PSPACE, and that it cannot be in promise-S2p unless the polynomial-time hierarchy collapses. Thus, under a reasonable complexity-theoretic assumption, multiplicative-factor approximation of succinct zero-sum games is strictly harder than additive-factor approximation.
Versions
- journal version in Computational Complexity 17:353-376, 2008.
- extended abstract in Proceedings of the Twentieth IEEE Conference on Computational Complexity (CCC'05), pages 323-332, 2005.