value problem, we use a transformation of instances of QSAT to POMDPs similar to the proof of Theorem 4.1   in (Mundhenk, b).

The set QSAT can be interpreted as a two-player game: Player 1 sets the existentially quantified variables, and player sets the universally quantified variables. Player 1 wins if the alternating choices determine a satisfying assignment to the formula, and player wins if the determined assignment is not satisfying. A formula is in QSAT if and only if player 1 has a winning strategy. This means player 1 has a response to every choice of player , so that in the end the formula will be satisfied.

The version where player makes random choices and player 1's goal is to win with probability - corresponds to SSAT ( stochastic satisfiability ), which is also PSPACE complete.  The instances of SSAT are formulas whi are quantified alternatingly with existential quantifiers and random quantifiers R . The meaning of the random quantifier R is that an assignment to the respective variable is chosen uniformly at random from 1. A
stochastic Boolean formula

$$\Phi\,=\,\quad\quad R\,\quad\quad\quad R$$

## Is In Ssat If And Only If

there exists

$$|\,\mathbf{y}\,\,\,\mathrm{if}$$

for random exists for random

* [10] M. C. Gonzalez-Garcia, M. C. Gonzalez-Garcia, M.  
random quantifiers, then the strategy of player 1 determines a set of  r If Φ has assignments to  . The term n) is true -" means that more than r-
(
of these     assignments satisfy From the proof of IP = PSPACE by Shamir (199 ) it follows that for every PSPACE
1 there is a polynomial-time reduction    from    to SSAT such that set and constant for every instance   and formula  (  ) =
R
x the following holds.

-), and I f , then for random n) is true (1 x ( if then for random n) is true r (

This means that player 1 either has a strategy under which she wins with very high probability, or the probability of winning (under any strategy) is very small. We show how to transform a stochastic Boolean formula Φ into a POMDP with a large history-dependent value if player 1 has a winning strategy, and a much smaller value if player wins.

For an instance Φ =
of SSAT, where Φ is a formula with varia bles R
n, we construct a POMDP   (Φ) as follows.  The role of player 1 is taken by the controller of the process. A strategy of player 1 determines a policy of the controller, and vice versa.  Player   appears as probabilistic transitions in the process.  The process
( ) has three stages. The first stage consists of one step. The process chooses uniformly at random one of the variables and an assignment to it, and stores the variable and the assignment. More formally, from the initial state _, one of the states _; = " (1 1 ) is reached, each with probability 1 (  ). It is not observable which variable assignment was stored by the process. However, whenever that variable appears later, the process checks that the initially fixed assignment is chosen again. If the policy gives a different assignment during the second stage, the process halts with reward . (There is a deterministic transition to a final state which we refer to as  end, or less formally, the dead end state.) If such an inconsistency occurs during the third stage, the process halts