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.

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.