作者
Stephen A Cook, Robert A Reckhow
发表日期
1972/5/1
图书
Proceedings of the fourth annual ACM symposium on Theory of computing
页码范围
73-80
简介
In this paper we introduce a formal model for random access computers and argue that the model is a good one to use in the theory of computational complexity. Results are proved which compare run times for recognizing sets using this model (which has a fixed program) with a stored program model and with Turing machines. The main result, theorem 3, shows the existence of a time complexity hierarchy which is finer than that of any standard abstract computer model. An Algol-like programming language is introduced which facilitates proofs of the theorems.
引用总数
学术搜索中的文章
SA Cook, RA Reckhow - Proceedings of the fourth annual ACM symposium on …, 1972