ON BOUNDED QUERIES AND APPROXIMATION

This paper investigates the computational complexity of approximating several NP-optimization problems using the number of queries to an NP oracle as a complexity measure. The results show a tradeoff between th e closeness of the approximation and the number of queries required. F or an approximation factor k(n), log log(k(n)) n queries to an NP orac le can be used to approximate the maximum clique size of a graph withi n a factor of k(n). However, this approximation cannot be achieved usi ng fewer than log log(k(n)) n - c queries to any oracle unless P = NP, where c is a constant that does not depend on k. These results hold f or approximation factors k(n) greater than or equal to 2 that belong t o a class of functions which includes any integer constant function, l og n, log(a) n, and n(1/a). Similar results are obtained for Graph Col oring, Set Cover, and other NP-optimization problems.