The Computational Complexity of Random Access Machines

计算复杂性理论的一个基本结果是图灵机的线性加速定理。该定理表明，对于时间复杂度为T(n)n的每一个多带图灵机，对于每一个常数c0，都存在一个在时间为cT(n)时接受相同语言的多带图灵机。一个问题是，线性加速会不会是图灵机模型的病态产物？这个项目包括确定哪些属性不是图灵机的工件。具体而言，研究了随机存取机（RAM）和两种相关模型——存储修改机（SMM）和并行随机存取机（PRAM）的计算复杂度。

One of the fundamental results in computational complexity theory is the linear speed-up theorem for turing machines. This theorem states that for every multitape turing machine of time complexity T(n)n and for every constant c0 there is a multitape machine that accepts the same language in time cT(n). One question is, could linear speed-up be a pathological artifact of the turing machine model? This project involves the determination of which properties are not artifacts of turing machines. Specifically, the computational complexity of the random access machine (RAM) and two related models, the storage modification machine (SMM) and the parallel random access machine (PRAM) will be investigated.