Some connections between nonuniform and uniform complexity classes
Some connections between nonuniform and uniform complexity classes
复制标题
非均匀和均匀复杂度类之间的一些联系
DOI：
10.1145/800141.804678
复制
发表时间：
1980
期刊：
影响因子：
--
通讯作者：
R. Lipton
中科院分区：
文献类型：
--
作者：
R. Karp;R. Lipton
众所周知，P中的每个集合都有小电路[13]。Adleman[1]最近证明了一个更强的结果，即随机图灵机在多项式时间内接受的每个集合都有小电路。这两个结果都是一致和非一致复杂性界限之间已知关系的典型。作为一致上界的结果，它们得到了一个不一致的上界。
这里的中心主题是试图探索相反的方向。也就是说，我们希望了解何时可以使用不一致的上界来获得一致的上界。
在本节中，我们将定义非一致复杂性的基本概念。然后我们将展示如何将它与更常见的概念联系起来。
It is well known that every set in P has small circuits [13]. Adleman [1] has recently proved the stronger result that every set accepted in polynomial time by a randomized Turing machine has small circuits. Both these results are typical of the known relationships between uniform and nonuniform complexity bounds. They obtain a nonuniform upper bound as a consequence of a uniform upper bound.
The central theme here is an attempt to explore the converse direction. That is, we wish to understand when nonuniform upper bounds can be used to obtain uniform upper bounds.
In this section we will define our basic notion of nonuniform complexity. Then we will show how to relate it to more common notions.