The Computational Complexity of 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.