Simultaneous resource bounds and parallel computation

The complexity theory of synchronous computation is studied in this thesis. It is shown that there is a precise relationship between space usage on traditional models of sequential computation and hardware usage on two new models of computation. These two new models of parallelism, called hardware modification machines and aggregates, are also shown to be closely related to existing models, such as combinational circuits; and variants of the new models are used to examine non-uniform and non-deterministic complexity classes. It is also shown that a close relationship exists between the reversal used in a sequential computation and the time used in a corresponding computation. Moreover, this new relationship can be made to hold simultaneously with the hardware/space relationship mentioned above. This simultaneous correspondence between sequential and resource usage can be used as evidence for an extended version of the parallel computation thesis, which attempts to relate the intuitive concepts of time and hardware to formal sequential resource usage. We study the interrelationships of these two resources, time and hardware, and show that to within polynomial factors, they define the same complexity classes. Finally, we examine some specific simultaneous complexity classes and show them to be the same as previously studied sequential simultaneous classes.