Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > ZERO-SUM GAMES:
Reports tagged with zero-sum games:
TR04-001 | 11th December 2003
Lance Fortnow, Russell Impagliazzo, Chris Umans

#### On the complexity of succinct zero-sum games

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) ... more >>>

TR09-055 | 10th June 2009
Venkatesan Chakaravarthy, Sambuddha Roy

#### Arthur and Merlin as Oracles

We study some problems solvable in deterministic polynomial time given oracle access to the (promise version of) the Arthur-Merlin class.
Our main results are the following: (i) $BPP^{NP}_{||} \subseteq P^{prAM}_{||}$; (ii) $S_2^p \subseteq P^{prAM}$. In addition to providing new upperbounds for the classes $S_2^p$ and $BPP^{NP}_{||}$, these results are interesting ... more >>>

ISSN 1433-8092 | Imprint