On uniform circuit complexity

Abstract

We consider uniform circuit complexity, introduced by Borodin as a model of parallel complexity. Three main results are presented. First, we show that simultaneous size/depth of uniform circuits is the same as space/time of alternating Turing machines, with depth and time within a constant factor and likewise log(size) and space. Second, we apply this to characterize the class of polynomial size and polynomial-in-log depth circuits in terms of tree-size bounded alternating TM's, in particular showing that context-free recognition is in this class of circuits. Third, we investigate various definitions of uniform circuit complexity, showing that it is fairly insensitive to the choice of definition.