We investigate hierarchical properties and logspace reductions of languages recognized by logspace probabilistic Turing machines, Arthur--Merlin games, and games against nature with logspace probabilistic verifiers. Each logspace complexity class is decomposed into a hierarchy based on corresponding two-way multihead finite-state automata and we (eventually) prove the separation of the hierarchy levels (even for languages over a single-letter alphabet); furthermore, we show efficient reductions of each logspace complexity class to, or between, low levels of its corresponding hierarchy. We find probabilistic and probabilistic-plus-nondeterministic variants of Savitch's maze threading problem which are logspace complete for PL (the class of languages recognized by logspace probabilistic Turing machines) and, respectively, PPP (the class of languages recognized by polynomial-time deterministic Turing machines), and which can be recognized by one-way non-sensing two-head (or one-way one-head one-counter) finite-state automata with probabilistic and both probabilistic and nondeterministic states, respectively.

Given a description of a probabilistic automaton (one-head probabilistic finite-state automaton or probabilistic Turing machine) and an input string x of length n, we ask how much space does a deterministic Turing machine need in order to decide the acceptance of the input string by that automaton? The question is interesting even in the case of one-head one-way probabilistic finite-state automata (1pfa's). We call (rational) stochastic languages} ($\SS_{rat}^{ > }$) the class of languages recognized by 1pfa's whose transition probabilities and cutpoints (i.e., recognition thresholds) are rational numbers. The class $\SS_{rat}^{ > }$ contains context-sensitive languages that are not context-free, but on the other hand there are context-free languages not included in $\SS_{rat}^{ > }$. Our main results are as follows: \begin{itemize} \item{ The (proper) inclusion of $\SS_{rat}^{ > }$ in $\zlo$, which is optimal (i.e., $\SS_{rat}^{ > } \not \subset$ \Dspace$(o(\log n))$). The previous upper bounds were \Dspace$(n)$ (obtained by P. D. Dieu in 1972) and\linebreak[4]\Dspace$(\log n \log \log n)$ (obtained by H. Jung in 1984).} \item{ Probabilistic Turing machines with space bound f(n) in O(log n) can be deterministically simulated in space $O(\min (c^{f(n)}\log n, \log n (f(n) + \log \log n)))$, where c is a constant depending on the simulated probabilistic Turing machine. The best previously known simulation uses O(log n (f(n) + log log n)) space (obtained by H. Jung in 1984).} \end{itemize} To obtain these results we develop and use two space-efficient (but also parallel-time-efficient) techniques, which are of independent interest: \begin{itemize} \item {a technique to compare deterministically, using only O(log n) space, large numbers given in terms of their values modulo a sequence of primes, p 1 < p 2 < \cdots < p n in O(n a ) (where a is some arbitrary constant);} \item {a technique to compare deterministically a threshold with entries of the inverse of a given banded matrix.} \end{itemize}

Properties of (unbounded-error) probabilistic as well as “probabilistic plus nondeterministic” pushdown automata and auxiliary pushdown automata are studied. These models are analogous to their counterparts with nondeterministic and alternating states. Complete characterizations in terms of well-known complexity classes are given for the classes of languages recognized by polynomial time-bounded, logarithmic space-bounded auxiliary pushdown automata with probabilistic states and with “probabilistic plus nondeterministic” states. Also, complexity lower bounds are given for the classes of languages recognized by these automata with unlimited running time. It follows that, by fixing an appropriate mode of computation, the difference between classes of languages such as P and PSPACE, NL and SAC1, PL and Diff>(#SAC1) is characterized as the difference between the number of stack symbols; that is, whether the stack alphabet contains one versus two distinct symbols.

Adapting a method that Freivalds used in the context of bounded-error probabilistic computation, we prove that the languages recognized by log-space unbounded-error probabilistic Turing machines (PL) are log-space reducible to languages recognized by automata of the same type but restricted to use at most ε log n bits of storage space, for arbitrarily small ε s 0. Furthermore, we show that the banded-matrix inversion problem Band-Mat-Inv(nε) is log-space complete for PL, for any ε ϵ (0, 1]. This strengthens a result of Jung that Band-Mat-Inv(n) is log-space complete for PL, and may lead to new space-efficient deterministic simulations of space-bounded probabilistic Turing machines.