Sequential, machine-independent characterizations of the parallel complexity classes AlogTIME, AC k , NC k and NC
Peter Clote · Birkhäuser Boston eBooks · 1990
In the spirit of A. Cobham’s algebraic, machine-independent characterization of the collection FP of polynomial time computable functions in [Cob65] (see also [Ros84]), we characterize the collection AC O of functions computable with uniform constant depth polynomial size circuits and the collection NC of functions computable in polylogarithmic time with a polynomial number of processors on a parallel random access machine (PRAM). From these characterizations, we obtain level-by-level characterizations of the intermediate classes AC k and NC k . The class AC O is the closure of certain simple initial functions under composition and a variant of bounded primitive recursion called concatenation recursion on notation. The class NC is obtained from the same initial functions by adding a second variant of bounded primitive recursion called weak bounded recursion on notation. Thus, well known parallel complexity classes are characterized in a machine-independent manner using sequential operations. As a corollary, one can give Backus-Naur for a sequential programming language fragment of Pascal which “captures” the parallel complexity class NC, in the sense that functions, which can be programmed in this fragment, are exactly those which are computable in polylogarithmic time with a polynomial number of processors on a PRAM Note that this latter result is much more than a simple serialization of parallel code.