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 \emph{exact} value of a succinct zero-sum game by
several results on \emph{approximating} the value. (1) We prove that
approximating the value of a succinct zero-sum game to within an
\emph{additive} factor is
\emph{complete} for the class $\promise\text{-}S_2^p$, the ``promise''
version of $S_2^p$. To the best of our knowledge, it is the first
natural problem shown complete for this class. (2) We describe a
$\ZPP^{\NP}$ 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 $\ZPP^{\NP}$ algorithm
for learning circuits for SAT~\cite{BCGKT96} and a recent result by
Cai~\cite{Cai01} that $S_2^p\subseteq\ZPP^{\NP}$. (3) We observe that
approximating the value of a succinct zero-sum game to within a
\emph{multiplicative} factor is in $\PSPACE$, and that it
\emph{cannot} be in $\promise\text{-}S_2^p$
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