文章基本信息

标题：Some Connections between Bounded Query Classes and Non-Uniform Complexity
本地全文：下载
作者：Amihood Amir ; Richard Beigel ; William Gasarch 等
期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2000
卷号：2000
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：Let A(x) be the characteristic function of A. Consider the function F_k^A(x_1,...,x_k) = A(x_1)...A(x_k). We show that if F_k^A can be computed with fewer than k queries to some set X, then A can be computed by polynomial size circuits. A generalization of this result has applications to bounded query classes, circuits, and enumerability. In particular we obtain the following. (1) Assuming Sigma_3^p <> Pi_3^p, there are functions computable using f(n)+1 queries to SAT that are not computable using f(n) queries to SAT, for f(n) = O(logn). (2) If F_k^A, restricted to length n inputs, can be computed by an unbounded fanin oracle circuit of size s(n) and depth d(n), with k-1 queries to some set X, then A can be computed with an unbounded fanin (non-oracle) circuit of size n^{O(k)}s(n) and depth d(n)+O(1).
关键词：bounded queries, circuits, Enumerability, Enumeration