Relationships between Probabilistic and Deterministic Tape Complexity

Abstract By giving a matrix inversion algorithm that uses a small amount of space, a result of Simon is improved: For constructible functions f(n)∉ o(logn) f(n) tape-bounded probabilistic Turing machines can be simulated on deterministic ones within (f(n)) 2 space.

Authors

• H. Jung

Keywords

No keywords are indexed for this paper.