Speedups of deterministic machines by synchronous parallel machines
Patrick W. Dymond, Martin Tompa · 1983
This paper presents the new speedups DTIME(T) @@@@ ATIME(T/log T) and DTIME(T) @@@@ PRAM-Time(@@@@T). These improve the results of Hopcroft, Paul, and Valiant that DTIME(T) @@@@ DSPACE(T/log T), and of Paul and Reischuk that DTIME(T) @@@@ ATIME(T log log T/log T). The new approach unifies not only these two previous results, but also the result of Paterson and Valiant that Size(T) @@@@ Depth(O(T/log T)).