Expressibility And Parallel Complexity

It is shown that the time needed by a concurrent-read, concurrentwrite parallel random access machine (CRAM) to check if an input has a certain property is the same as the minimal depth of a firstorder 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 AC i ; i 1 is given by first-order sentences "iterated" log i n times. Similarly, uniform 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. Key words. Computational c..