Probabilistic Models of Computation

Thesis (Ph. D.)--University of Rochester. Dept. of Computer Science, 1995. Published in the Technical Report series in 2000.We present hierarchical characterizations and reductions of classes of languages recognized by logarithmic-space (logspace, for short) probabilistic Turing machines, and by Arthur-Merlin games and games against Nature, both with logspace probabilistic verifiers. We decompose each logspace complexity class into a hierarchy based on the corresponding multihead two-way finite automata, and we prove that most of these hierarchies are strict, even with respect to languages over a single-letter alphabet. We also obtain efficient reductions of our logspace complexity classes to low levels in the corresponding hierarchies. Another focus is on space-efficient deterministic simulation of space-bounded Turing machines with probabilistic and mixed (i.e., probabilistic and nondeterministic) transitions. We present new results for two classes of machines, defined respectively in terms of logarithmic and sublogarithmic space bounds: 1) For logarithmic bounds, we obtain several new complete problems. These include variants of Savitch's maze-threading problem that are solvable by surprisingly simple devices. In particular, it follows that matrix inversion problems, which seem computationally hard, are efficiently reducible to languages recognized by one-way probabilistic devices that seem quite weak. 2) For sublogarithmic bounds, we find deterministic simulations significantly more space-efficient than the previously known simulations. In particular, for one-head probabilistic finite automata, we obtain an optimal, logspace deterministic simulation. Since our simulations are presented in the more general setting of Markov chains, they may have other applications as well. For use in the simulations, we develop space-efficient (and parallel-time-efficient) deterministic techniques for working with succinct residue representations of large natural numbers. We extend our study to pushdown automata and auxiliary-pushdown automata with probabilistic and mixed transitions. We give characterizations in terms of well-known complexity classes for the classes of languages recognized by these automata. It follows that the differences between classes of languages such as P and PSPACE, NL and SAC^1, and PL and Diff_>(#SAC^1) all derive from the difference between using one symbol and using two symbols on a pushdown store, in certain settings. Finally, we define and investigate probabilistic automata with "logspace-constructible" transition probabilities