Linear-Time Computation and Low-Level Complexity

9409104 Regan本研究将分析在线性时间内可解的计算问题，或属于非常小的均匀电路类的计算问题。线性时间并没有得到多项式时间概念那么多的关注，并且被认为缺乏一个好的机器模型。先前的工作已经开发了“块移动”（BM）模型，这是Aggarwal， Chandra和Snir的“块转移”（BT）模型的重要扩展，并表明BM具有良好的鲁棒性和线性时间的通用仿真特性，并表征了一些低级电路类。目前的工作将使用BM给出的新工具来处理时间上的非线性下界和对低级复杂性类的更深入分析。BM将对数据的“随机”访问视为具有有形成本（如在真实机器中观察到的那样），并量化内存延迟和有形成本（如在真实机器中观察到的那样），并量化内存延迟和处理器与数据之间的通信延迟。解决一个问题需要多少随机访问的问题与决定论与非决定论这一较老的经典问题有关。下界的新方法有待进一步研究，这项工作将从信息结构的角度分析计算问题，而不是特定的机器模型。＊＊＊

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. ***