Structure of LOG-Space Probabilistic Complexity Classes

摘要

We investigate hierarchical properties and log-space reductions of languagesrecognized by log-space probabilistic Turing machines, Arthur-Merlin games and Games against Nature with log-space probabilistic verifiers. For each log-space complexity class, we decompose it into a hierarchy based on corresponding multihead two-way finite automata and we (eventually) prove the separation of the hierarchy levels (even over one letter alphabet); furthermore, we show 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 which are log-space complete for PL (and respectively P) and can be recognized by two-head one-way and one-way one-counter finite automata with probabilistic (probabilistic and nondeterministic) states.