作者
Stephen A Cook
发表日期
1972/5/1
图书
Proceedings of the fourth annual ACM symposium on Theory of computing
页码范围
187-192
简介
The purpose of this paper is to prove the following result:
Theorem 1 For any real numbers r1, r2, 1 ≤ r1 < r2, there is a set A of strings which has nondeterministic time complexity nr2 but not nondeterministic time complexity nr1
The computing devices are non-deterministic multitape Turing machines.
引用总数
19851986198719881989199019911992199319941995199619971998199920002001200220032004200520062007200820092010201120122013201420152016201720182019202020212022202320245432446233236151146964986885135121310795156142
学术搜索中的文章
SA Cook - Proceedings of the fourth annual ACM symposium on …, 1972