The Computational Complexity of Random Access Machines

随机存取机的计算复杂性

• 批准号: 8922008
• 负责人: Michael Loui
• 金额: $ 5.57万
• 依托单位: University of Illinois at Urbana-Champaign
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 1990
• 资助国家: 美国
• 起止时间: 1990-07-15 至 1993-12-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=8922008&HistoricalAwards=false
• 关键词: Computational; Complexity; Random; Access; Machines

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.

计算复杂性理论的一个基本结果是 图灵机的线性加速定理 该定理指出， 对于时间复杂度为T（n）n的多带图灵机， 对于每个常数c0，都有一个多带机接受 时间上相同的语言cT（n）。 一个问题是，线性加速 是图灵机模型的病态产物吗 这个项目 包括确定哪些属性不是 图灵机 具体来说， 随机存取机（RAM）和两个相关的模型，存储 修改机（SMM）和并行随机存取机 （PRAM）将进行调查。