On small space complexity classes of stochastic turing machines and Arthur-Merlin-games

A Stochastic Turing machine (STM) Is a luring machine that can perform nond eterministic and probabilistic moves and alternate between both types. Such devices are also called games against nature, Arthur-Merlin-games, or inte ractive proof systems with public coins. We investigate stochastic machines with space resources between constant and logarithmic size, and, in additi on, constant or sublinear bounds on the number of alternations between nond eterministic and probabilistic moves. Lower space bounds are shown for a sp ecific family of languages by exploiting combinatorial properties. These re sults imply an infinite hierarchy with respect to the number of alternation s of STMs, and nonclosure properties of certain classes.