Linear-Time Computation and Low-Level Complexity

9409104里根这项研究将分析计算问题是可解决的线性时间，或属于非常小的统一电路类。 线性时间没有像多项式时间那样受到关注，并且被认为缺乏一个好的机器模型。 以前的工作已经开发了“块移动”（BM）模型，这是一个显着的扩展的“块传输”（BT）模型的Aggarwal，钱德拉，和Snir，并显示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. ***