Speedups of deterministic machines by synchronous parallel machines

摘要

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 (J. Assoc. Comput. Mach. 24 (1977), 332–337) that DTIME(T)⊆DSPACE(T/logT), and of Paul and Reichuk (Acta Inform. 14 (1980), 391–403) 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 (Theoret. Comput. Sci. 2 (1976), 397–400) that Size(T)⊆Depth(O(T/log T)).