9409104 Regan This research will analyze computational problems which are solvable in linear time, or which belong to very small uniform circuit classes. Linear time has not received nearly as much attention as the concept of polynomial time, and has been considered to lack a good machine model. Previous work has developed the "Block Move" (BM) model, which is a significant extension of the "Block Transfer" (BT) model of Aggarwal, Chandra, and Snir, and showed the BM to have good properties of robustness and universal simulation for linear time, and to characterize some of the low-level circuit classes. The present work will use new tools given by the BM for nonlinear lower bounds on time and for deeper analysis of low-level complexity classes. The BM treats "random" access to data as having tangible cost, as observed with real machines, and quantifies memory latency and tangible cost, as observed with real machines, and quantifies memory latency and communication delays between processors and data. The question of how much random access is needed to solve a problem is related to older classic problems of determinism versus nondeterminism. A new approach to lower bounds is to be pursued further, this work will analyze computational problems in terms of information structures apart from particular machine models. ***
