On the complexity of succinct zero-sum games

Lance Fortnow, Russell Impagliazzo, Valentine Kabanets, and Chris Umans


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.