Space-bounded hierarchies and probabilistic computations (Q1062759)

First the paper gives a simple proof of Simon's result that space-bounded probabilistic complexity classes are closed under complement. Main results concern new definition of space-bounded ''oracle hierarchy''. The entire log n space ''alternation hierarchy'' is contained in the 2nd level of the log n space ''oracle hierarchy''. However, the entire log n space ''oracle hierarchy'' is contained in bounded-error probabilistic space log n. This entails interesting consequences.