RSPACE(S) \subseteq DSPACE(S 3/2 )

We prove that any language that can be recognized by a randomized algorithm (with possibly two-sided error) that runs in space S and expected time 2/sup 0(s)/ can be recognized by a deterministic algorithm running in space S/sup 3/2/. This improves over the best previously known result that such algorithms have deterministic space S/sup 2/ simulations which, for one-sided error algorithms, follows from Savitch's Theorem and for two-sided error algorithms follows by reduction to recursive matrix powering. Our result includes as a special case the result due to N. Nisan et al. (1992), that undirected connectivity can be computed in space log/sup 3/2/n. It is obtained via a new algorithm for repeated squaring of a matrix we show how to approximate the 2/sup /spl tau// power of a d/spl times/d matrix in space /spl tau//sup 1/2/ log d, improving on the bo und of /spl tau/ log d that comes from the natural recursive algorithm. The algorithm employs Nisan's pseudorandom generator for space bounded computation, together with some new techniques for reducing the number of random bits needed by an algorithm.

Authors

• Michael E. Saks
• Shiyu Zhou

Keywords

• Computational modeling
• Extraterrestrial measurements
• Stochastic processes
• Mathematics
• Computer science
• USA Councils
• Turing machines
• Magnetic heads
• Terminology
• Probability distribution
• Deterministic
• Pseudo-random
• Recursive Algorithm
• Random Bits
• Real Numbers
• Efficient Algorithm
• Proof Of Theorem
• Estimation Algorithm
• Error Probability
• Function Matrix
• Space Complexity
• Matrix M
• Square Matrix
• Transition Probability Matrix
• Probability 2
• Statistical Dependence
• Space Requirements
• Properties Of Algorithm
• Perfect Square
• Matrix Algorithm