Abstract of Paper

On Probabilistic Quantified Satisfabilty Games
by Marcin Rychlik

Abstract:

We study the complexity of some new probabilistic variant of the problem
Quantified Satisfability(QSAT). Let a sentence $\exists v_{1}\forall v_{2}\ldots \exists v_{n-1}\forall v_{n}\phi$ be given. In classical game
associated with the QSAT problem, the players $\exists$ and $\forall$
alternately chose Boolean values of the variables $v_{1},\ldots ,v_{n}$. In
our game one (or both) players can instead determine the probability that $% v_{i}$ is true. We call such player a \emph{probabilistic player} as
opposite to \emph{classical player}. The payoff (of $\exists$) is the
probability that the formula $\phi$ is true. We study the complexity of the
problem if $\exists$ (probabilistic or classical) has a strategy to achieve
the payoff at least $c$ playing against $\forall$ (probabilistic or
classical). We completely answer the question for the case of threshold $c=1$%
, exhibiting that the case when $\forall$ is probabilistic is easier to
decide ($\Sigma _{2}^{P}$--complete) than the remaining cases
(PSPACE-complete).

For thresholds $c<1$ we have a number of partial results. We establish
PSPACE-hardness of the question whether $\exists$ can win in the case when
only one of the players is probabilistic, and $\Sigma _{2}^{P}$%
-hardness when both players are probabilistic. We also show that the set of
thresholds $c$ for which a related problem is PSPACE is dense in
$\left[ 0,1\right]$.

We study the set of reals $c\in \lbrack 0,1]$ that can be game values of our
games. The set turns out to include the set of binary rationals, but also
some irrational numbers.