Space-bounded hierarchies and probabilistic computations
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.
space-bounded probabilistic complexity classes
scientific article; zbMATH DE number 3915628
scientific article