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.