文章基本信息

标题：Gaps in Bounded Query Hierarchies
本地全文：下载
作者：Richard Beigel
期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：1998
卷号：1998
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：
Prior results show that most bounded query hierarchies cannot contain finite gaps. For example, it is known that P_(m+1)-tt^SAT = P_m-tt^SAT implies P_btt^SAT = P_m-tt^SAT and for all sets A
- FP_(m+1)-tt^A = FP_m-tt^A implies FP_btt^A = FP_m-tt^A
- P_(m+1)-T^A = P_m-T^A implies P_bT^A = P_m-T^A
- FP_(m+1)-T^A = FP_m-T^A implies FP_bT^A = FP_m-T^A
where P_m-tt^A is the set of languages computable by polynomial-time Turing machines that make m nonadaptive queries to A; P_btt^A = U_mP_m-tt^A; P_m-T^A and P_bT^A are the analogous adaptive queries classes; and FP_m-tt^A, FP_btt^A, FP_m-T^A, and FP_bT^A in turn are the analogous function classes.
关键词：bounded queries, bounded query class, bounded queryhierarchy, bounded truth table, GAP, nonadaptive queries, P, P/poly, polynomial time, polynomialadvice, recursion theory, reduction, truth table, upward collapse