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.