Lower Bounds for Probabilistic Space Complexity: Automata Approach
Farid Mansurovich Ablayev · UR Research (University of Rochester) · 1992
In this paper we investigate a well known sequential model of computation: one-way LOG-SPACE Turing machines. We analyze a different known method for constructing an effective probabilistic algorithm. We prove a lower bound for probabilistic space complexity, which is good enough for understanding the above problem for the one-way LOG-SPACE Turing machine model of computation.