[PDF][PDF] A hierarchy for nondeterministic time complexity
SA Cook - Proceedings of the fourth annual ACM symposium on …, 1972 - dl.acm.org
Proceedings of the fourth annual ACM symposium on Theory of computing, 1972•dl.acm.org
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.
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.
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.
ACM Digital Library以上显示的是最相近的搜索结果。 查看全部搜索结果