BP_H SPACE(S ) is contained in DSPACE(S~3/2 )

摘要

We prove that any language that can be recognized by a randomized algo- rithm (with possibly a two-sided error) that runs in space O(S) and always terminates can be recognized by deterministic algorithm running in space O(S~3/2). This improves the best previously known result that such algorithms have deterministic space O(S~2) simulations which, for one-sided error algo- rithms, 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 Nisan, Szemeredi, and Wigderson that undirected connectivity can be computed in space O(log~(3/2) n). It is obtained via a new algorithm for repeated squaring of a matrix; we show how to approximate the 2'th power of a d × d matrix in space O(r~(1/2) log d), improving on the bound of O(r log d) that comes from the natural recursive algorithm. The algorithm employs Nisan's pseudorandom generator for space-bounded com- putation, together with some new techniques for reducing the number of random bits needed by an algorithm.