A hierarchy for nondeterministic time complexity
A hierarchy for nondeterministic time complexity
复制标题
不确定时间复杂度的层次结构
DOI：
10.1145/800152.804913
复制
发表时间：
1972
期刊：
影响因子：
--
通讯作者：
S. Cook
中科院分区：
文献类型：
--
作者：
S. Cook
Please try later.
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.