Complexity theory of parallel time and hardware (Q1116695)

The parallel resources time and hardware and the complexity classes defined by them are studied using the aggregate model. The equivalence of complexity classes defind by sequential space and uniform aggregate hardware is established. Aggregate time is related to (bounded fanin) circuit depth and, similarly, aggregate hardware is relaed to circuit width. Interelationships between aggregate time and hardware follow as corollaries. Aggregate time is related to the sequential resource reversal. Simultaneous relationships from aggregate hardware and time to sequential space and reversal are shown (and conversely), and these are used as evidence for an ``extended parallel computation thesis''. These simultaneous relationships provide new characterizations for the simultaneous parallel complexity class NC and for the complementary class SC. The evaluation of monotone planar circuits is shown to be in NC, in fact in LOGCFL.