Characterizations of parallel complexity classes
H. Venkateswaran · 1986
A new two-person pebble game that abstracts the control structure of many parallel algorithms is defined and studied. This game extends the two-person pebble game defined by Dymond and Tompa (JCSS, Vol. 30, no. 2, 1985, pp. 149-161) in two ways: (a) the game is played on a Boolean circuit rather than on an unlabelled graph, and takes into consideration the types of the gates in the circuit, and (b) the two players' roles are completely symmetric. The new game is used to study the relationship between two natural parallel complexity classes, namely LOGCFL and AC('1). LOGCFL is the class of languages log space reducible to context-free languages. AC('1) is the class of languages accepted by an alternating Turing machine in space O(log n) and alternation depth O(log n). LOGCFL is a subclass of AC('1), but it is not known whether the inclusion is proper. For many problems in LOGCFL the algorithms that show their membership in that class also show their membership in AC('1). However, these algorithms do not use the full power of AC('1) computations. The two-person game defined here provides a model of computation in which this perceived difference can be quantified. This is done by characterizing the two classes using the same measures of resources in the game model. The results so obtained not only illustrate the similarity between these two classes, but also isolate a fundamental difference between them: the recognition of languages in LOGCFL does not utilize the symmetry between the two players, whereas the recognition of languages in AC('1) does. A resource that captures this difference, called role switches, is identified in the game model: languages in LOGCFL use no role switches, whereas languages in AC('1) use O(log n) role switches. Thus the results indicate why the two classes may not be equal. As another application of this game, it is shown that the game model unifies in a single framework the proofs of the following three well known results of complexity theory: (1) Savitch's theorem that nondeterministic space S is contained in deterministic space S('2), (2) Ruzzo's NC algorithm for context-free language recognition, and (3) Borodin and Ruzzo's simulation of simultaneous space and alternation bounded alternating Turing machines by simultaneous space and time bounded alternating Turing machines. Motivated by the characterizations in terms of the game, a property called semi-unboundedness is defined for the following four models: alternating Turing machines, nondeterministic auxiliary pushdown automata, bounded fan-in Boolean circuits, and unbounded fan-in Boolean circuits. This is used in obtaining new characterizations of LOGCFL on these models. Three of these characterizations are in terms of the same measures of resources used to characterize AC('1) on these models, and provide supporting evidence to the belief that these two classes are not equal.