On the structure of log-space probabilistic complexity classes

We investigate hierarchies of complexity classes defined by log-space probabilistic Turing machines, Arthur-Merlin games and Games against nature with logarithmic space-bounded probabilistic verifiers. We decompose each log-space complexity class into a hierarchy based on corresponding multihead two-way finite-state automata and we prove the separation of the levels of several hierarchies even over a one letter alphabet; furthermore, we show deterministic log-space reductions of each log-space complexity class to low levels of its corresponding hierarchy.We find probabilistic (and “probabilistic+nondeterministic”) variants of Savitch's maze threading problem that are log-space complete for PL (and respectively P) and that can be recognized by two-head one-way and one-head one-way one-counter finite-state automata with probabilistic (probabilistic and nondeterministic) states.