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.