  We consider two-player partial-observation stochastic games on finite-state
graphs where player 1 has partial observation and player 2 has perfect
observation. The winning condition we study are \omega-regular conditions
specified as parity objectives. The qualitative-analysis problem given a
partial-observation stochastic game and a parity objective asks whether there
is a strategy to ensure that the objective is satisfied with probability~1
(resp. positive probability). These qualtitative-analysis problems are known to
be undecidable. However in many applications the relevant question is the
existence of finite-memory strategies, and the qualitative-analysis problems
under finite-memory strategies was recently shown to be decidable in 2EXPTIME.
We improve the complexity and show that the qualitative-analysis problems for
partial-observation stochastic parity games under finite-memory strategies are
EXPTIME-complete; and also establish optimal (exponential) memory bounds for
finite-memory strategies required for qualitative analysis.
