__
Revision #1 to TR97-035 | 22nd April 1999 00:00
__
#### ... the title of revised version (even if it is the same) Revision of: TR97-035

**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.

__
TR97-035 | 31st July 1997 00:00
__

#### Bounded Queries, Approximations and the Boolean Hierarchy

**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.