Linear-Time Computation and Low-Level Complexity

9409104里根这项研究将分析在线性时间内可解的计算问题，或属于非常小的统一电路类的计算问题。线性时间没有受到多项式时间概念那么多的关注，而且一直被认为缺乏一个好的机器模型。前人的工作发展了“块移动”(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. ***