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.

Abstract:
This paper introduces a new model of computation for describing the complexity of NP-approximation problems. The results show that the complexity of NP-approximation problems can be characterized by classes of multi-valued functions computed by nondeterministic polynomial time Turing machines with a bounded number of oracle queries to an NP-complete language. In contrast to the bounded query classes used in previous studies, the machines defined here solve NP-approximation problems by providing the witness to an approximate solution --- not just by estimating the size of the objective function. Furthermore, the introduction of this new model of computation is justified in three ways. First, the definition of these complexity classes is robust. Second, NP-approximation problems are complete problems for these complexity classes. This paper concentrates on the Traveling Salesman Problem and the MaxClique Problem. However, these results are general enough to extend to problems such as Graph Coloring and Maximum Satisfiability using existing techniques in the literature. Finally, the utility of this model of computation is demonstrated by proving some new upward collapse results for NP-approximation problems that would be difficult to achieve without the machinery provided by the model.