首页 | 本学科首页   官方微博 | 高级检索  
     


Bounded Queries, Approximations, and the Boolean Hierarchy
Authors:Richard Chang
Affiliation:Department of Computer Science and Electrical Engineering, University of Maryland Baltimore County, 1000 Hilltop Circle, Baltimore, Maryland, 21250, f1
Abstract:This paper investigates nondeterministic bounded query classes in relation to the complexity of NP-hard approximation problems and the Boolean Hierarchy. Nondeterministic bounded query classes turn out be rather suitable for describing the complexity of NP-hard approximation problems. The results in this paper take advantage of this machine-based model to prove that in many cases, NP-approximation problems have the upward collapse property. That is, a reduction between NP-approximation problems of apparently different complexity at a lower level results in a similar reduction at a higher level. For example, if M C reduces to (log n)-approximating M C using many–one reductions, then the Traveling Salesman Problem (TSP) is equivalent to M C under many–one reductions. Several upward collapse theorems are presented in this paper. The proofs of these theorems rely heavily on the machinery provided by the nondeterministic bounded query classes. In fact, these results depend on a surprising connection between the Boolean hierarchy and nondeterministic bounded query classes.
Keywords:
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号