期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：1997
卷号：1997
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：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.
