Expressibility and Parallel Complexity
Neil Immerman · SIAM Journal on Computing · 1989
It is shown that the time needed by a concurrent-read, concurrent-write parallel random access machine (CRAM) to check if an input has a certain property is the same as the minimal depth of a first-order inductive definition of the property. This in turn is equal to the number of “iterations” of a first-order sentence needed to express the property. The second contribution of this paper is the introduction of a purely syntactic uniformity notion for circuits. It is shown that an equivalent definition for the uniform circuit classes ${\text{AC}}^i ,i \geqslant 1$ is given by first-order sentences “iterated” $\log ^i n$ times. Similarly, uniform ${\text{AC}}^0 $ is defined to be the first-order expressible properties (which in turn is equal to constant time on a CRAM by our main theorem). A corollary of our main result is a new characterization of the Polynomial-Time Hierarchy (PH): PH is equal to the set of languages accepted by a CRAM using exponentially many processors and constant time.