TR04-001 Authors: Lance Fortnow, Russell Impagliazzo, Chris Umans

Publication: 10th January 2004 21:35

Downloads: 897

Keywords:

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.