Parallelizing Time with Polynomial Circuits

We study the problem of asymptotically reducing the runtime of serial computations with circuits of polynomial size. We give an algorithmic size-depth tradeoff for parallelizing time t random access Turing machines, a model at least as powerful as logarithmic cost RAMs. Our parallel simulation yields logspace-uniform t (O(1)) size, O(t/log t)-depth Boolean circuits having semi-unbounded fan-in gates. In fact, for appropriate d, uniform t (O(1))2 (O(t/d)) size circuits of depth O(d) can simulate time t. One corollary is that every log-cost time t RAM can be simulated by a log-cost CRCW PRAM using t (O(1)) processors and O(t/log t) time. This improves over previous parallel speedups, which only guaranteed an Omega(log t)-speedup with an exponential number of processors for weaker models of computation. These results are obtained by generalizing the well-known result that DTIME[t] subset of ASPACE[log t].