作者
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.
引用总数
学术搜索中的文章
SA Cook - Proceedings of the fourth annual ACM symposium on …, 1972