Parallel complexity hierarchies based on PRAMs and DLOGTLME-uniform circuits
Kazuo Iwama, Chihiro Iwamoto · 2002
Unlike the case of logspace-uniform circuits, complexity hierarchies do exist for PRAMs and DLOGTIME-uniform circuits: (i) There exist a constant d and a language L such that L is recognizable in time dT(n) by some PRIORITY CRCW PRAM but is not recognizable in time T(n) by any PRIORITY CRCW PRAM if the number of processors is fixed. (ii) There exist constants c, d and a language L such that L is recognizable by some family of DLOGTIME-uniform circuits of size (Z(n))/sup c/ and depth dT(n) but is not recognizable by any family of DLOGTIME-uniform circuits of size Z(n) and depth T(n) if T(n) is not bounded by O(log n).