BPHSPACE(S)⊆DSPACE(S3/2)

摘要

We prove that any language that can be recognized by a randomized algorithm (with possibly a two-sided error) that runs in spaceO(S) and always terminates can be recognized by deterministic algorithm running in spaceO(S3/2). This improves the best previously known result that such algorithms have deterministic spaceO(S2) 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 Nisan, Szemerédi, and Wigderson that undirected connectivity can be computed in spaceO(log3/2 n). It is obtained via a new algorithm for repeated squaring of a matrix; we show how to approximate the 2rth power of ad×dmatrix in spaceO(r1/2 log d), improving on the bound ofO(r 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.