Bounded Queries, Approximations and the Boolean Hierarchy

Author: R. Chang
Cite as: Information and Computation, 169(2):129-159, September 2001.
Previous incarnations:
- Technical Report TR 97-035, Electronic Colloquium on Computational Complexity, 1997.
- Technical Report TR CS-97-04, Department of Computer Science and Electrical Engineering, University of Maryland Baltimore County, July 1997.
Most readable version: journal version.
Status: complete.
Online:
- Article in Elsevier's Science Direct: DOI 10.1006/inco.2000.2884.
- Journal resubmission version available as a PDF file (with embedded Type 1 fonts): npfsat.pdf.

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 MaxClique reduces to log n-approximating MaxClique using many-one reductions, then the Traveling Salesman Problem (TSP) is equivalent to MaxClique 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.

Last Modified: 22 Jul 2024 11:27:54 EDT by Richard Chang