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.
展开▼
