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 the closeness of the approximation and the number of queries  required.  For an approximation factor $k(n)$, $\log \log_{k(n)} n$  queries to an \NP\ oracle can be used to approximate the maximum  clique size of a graph within a factor of $k(n)$.   However, this approximation cannot be achieved using fewer than  $\log \log_{k(n)} n - c$ queries to any oracle unless  is a constant that does not depend on $k$.   These results hold for approximation factors $k(n) \geq 2$ that  belong to a class of functions which includes any integer constant  function, $\log n$, $\log^{a} n$, and $n^{1/a}$.  Similar results  are obtained for Graph Coloring, Set Cover, and other \NP-optimization problems.
Introduction
The approximability of NP-optimization problems is a central theme both in the study of
algorithms and in computational complexity theory. Most NP-optimization problems have
decision versions that are NP-complete and are hence equivalent to each other as decision
problems. However, the approximability of the optimization problems may vary greatly.
For some NP-optimization problems, there are efficient algorithms that find good approximate
solutions. For others, no such algorithm can exist unless some standard intractability
assumption is violated (e.g., or the Polynomial Hierarchy collapses). Recently,
Arora, Lund, Motwani, Sudan and Szegedy [ALM showed that the problem of finding
the largest clique in a graph is in the latter category. Following a series of breakthrough
results [AS92, BFL91, FGL showed that there exists a constant ffl
such that no deterministic polynomial time algorithm can approximate the maximum clique
size !(G) of a graph G with n vertices within a factor of n ffl , unless . While this result
strongly suggests that no efficient algorithm can find good approximations to the maximum
clique problem, it does not resolve all of the questions about the computational complexity
of approximating the maximum clique size of a graph. In particular, it is not clear what
computational resources are sufficient and/or necessary to compute an approximation of the
maximum clique size using any of the traditional resource bounded measures (e.g., time,
space, random bits and alternation).
In this paper we use the number of queries to an NP-complete oracle as a complexity
measure. Krentel [Kre88] used this measure to show that the maximum clique size is complete
for polynomial time functions which use only O(log n) queries, denoted PF NP [O(log n)] . Since
Krentel's original work, many connections between bounded query classes and standard
complexity classes have been discovered [ABG90, AG88, Bei87, Bei91, CK90, GKR, Wag86,
WW85]. In many circumstances, these results show that one cannot decrease the number of
queries needed to solve a problem by even a single query, unless collapses. For
example, Hoene and Nickelsen [HN93] showed that to determine how many of the formulas
in F are satisfiable, dlog(r 1)e queries are both sufficient and necessary (unless
naive binary search can determine the number of satisfiable formulas using
queries to the NP oracle. The number of queries needed is dlog(r
than dlog re because there are r answers ranging from 0 to r. A tree pruning
technique shows that no polynomial time machine can determine the number of satisfiable
formulas using one fewer query to any oracle unless . Thus, the algorithm which
uses the fewest queries is simply the naive binary search algorithm. In this paper, we show
that approximating several NP-optimization problems also have this property. In the first
parts of the paper, we will focus on the complexity of approximating the size of the maximum
clique in a graph.
In order to state the results in this paper correctly we need to be more precise with the
term "approximation". Let !(G) denote the size of the maximum clique in the graph G.
We say that a number x is an approximation of !(G) within a factor of k(n) if !(G)=k(n)
x  !(G). Our results show a tradeoff between the closeness of the approximation and
the number of queries needed to solve the approximation problem-closer approximations
require more queries.
For example we can approximate !(G) within a factor of 2 using only log log n queries to
Factor Upper bound Lower bound (unless
log log n log log
log log n \Gamma log log k log log
log a n log log n \Gamma log log log a n log log n \Gamma log log log a
1=a log a log a \Gamma log 1=ffl

Table

1: Upper and lower bounds for approximating the maximum clique size.
NP, where n is the number of vertices in the graph G. In contrast, computing !(G) exactly
can be done with log n queries and
n) queries (unless
Moreover, we show that no function using fewer than (log log n) \Gamma log 1=ffl queries to any
oracle can approximate !(G) within a factor 2 unless (Here ffl is the constant given
in Corollary 3 of [ALM + 92].) In general our results show that for any "nice" approximation
factor k(n)  2, !(G) can be approximated within a factor of k(n) using log log k(n) n queries
but not with fewer than log log k(n) queries to any oracle unless In
Corollary 6, we show that the difference, log 1=ffl, between the upper and lower bounds has
a natural interpretation. Table 1 summarizes our results for some common approximation
factors.
We make a few observations about these results. First, since ffl is a constant, for a
large enough constant k, log log k would exceed log 1=ffl. Hence, for this k, the upper bound
on approximating !(G) within a factor of k will be strictly less than the lower bound for
approximating within a factor of 2. Hence, for this large k the problem of approximating
within a factor k has strictly lower complexity in terms of the number of queries than
approximating within a factor of 2 unless Similarly, approximating within a factor
of log n has a lower complexity than approximating within any constant; and approximating
within a factor of n 1=k has an even lower complexity. We believe that these are the first results
which show a tradeoff between complexity and closeness of approximation. In contrast,
Garey and Johnson [GJ79] showed that if !(G) can be approximated within a constant
factor in P then it can be approximated within any constant factor in P. While these are
not contradictory theorems, they certainly have very different flavors.
In the next section, we state the lemmas, definitions and notations needed to prove the
results. In Section 3, we show that a uniform binary search routine provides the upper
bounds we have mentioned. To prove the lower bound results, we start in Section 4.2 with
a simple proof which shows that no function in PF X[1] , for any oracle X, can approximate
within a factor of 2, unless We go on to the proof of the general lower
bound results. In Section 5 we discuss how these results extend to other NP optimization
problems (e.g., Chromatic Number). In Section 6, we ponder upon the value of the constant
ffl. Finally, in Section 7 we combine our techniques with the results of Lund and Yannakakis
[LY94] on the hardness of approximating the Set Cover problem to derive upper and lower
bounds on the query complexity of approximating the minimum set cover size.
Preliminaries
Definition 1 For every graph G, let jGj denote the number of vertices in the graph and let
!(G) denote the size of the largest clique in G. We say that a function A(G) approximates the
maximum clique size within a factor of k(n) if for all graphs G with n vertices !(G)=k(n)
Some papers use the alternative condition that !(G)=k(n)  A(G)  k(n) \Delta !(G), but
we find it unintuitive to consider A(G) an approximation of !(G) if there does not exist a
clique of size A(G) in G. However, the results in this paper still hold under the alternative
definition.
To prove the lower bounds, we need the result of Arora et al [ALM + 92] which showed
that there exists an ffl ? 0 such that the maximum clique size cannot be approximated within
a factor of n ffl in deterministic polynomial time unless is the number of
vertices in the graph. Their construction yields the next lemma.
There exist constants s, b and d, d, such that given
a Boolean formula F with t variables, we can construct in polynomial time a graph G with
vertices, where
The constants b, s and d will be fixed for the remainder of the paper. Of particular interest
is the ratio (b \Gamma s)=d, because it is equal to the ffl mentioned before Lemma 2. To prove the
intractability of n ffl approximation, first assume that we have a polynomial time algorithm
to approximate !(G) within n ffl . Take any Boolean formula F , and let t be the number of
variables in F . Construct G as described in Lemma 2. Use the polynomial time algorithm to
obtain an approximation x of !(G). Since , an n ffl approximation is within a factor
of (t d the algorithm must guarantee that x  t b =t On the
other hand, if F 62 SAT then x
Definition 3 Let PF X[q(n)] be the class of functions computed by polynomial time oracle
Turing machines which ask at most q(n) queries to the oracle X. Since the queries are
adaptive, the query strings may depend on answers to previous queries.
3 Upper bounds
We first examine the upper bounds on the complexity of approximating NP-optimization
problems in terms of bounded query classes. The general idea is to use each query to SAT
to narrow down the range where the optimal solution exists. For example, for a graph G
with n nodes, 1  !(G)  n. We can compute !(G) exactly using binary search and log n
queries of the form: "Is !(G) greater than x?"
On the other hand, to approximate !(G) within a factor of 2, we only need to find a
number x such that x  !(G)  2x. Thus, we first partition the numbers from 1 to n into
the intervals
ne
If !(G) is in the interval then we can simply use 2 i as a factor 2 approximation
of !(G). Thus, our strategy is to use binary search on the left endpoints of the intervals to
determine which interval contains !(G). Since there are only dlog ne intervals, we only need
dlog dlog nee queries to SAT to perform this binary search. In the general case, if we want
to find an approximation of !(G) that is within a factor of k(n), there will be
l
log k(n) n
intervals of the form (k(n) binary search would use
l
log
l
log k(n) n
mm
queries to
SAT. Thus, we have the following lemma.
Lemma 4 Let k(n) be a polynomial time computable function such that 1
there exists a function in PF SAT [dlogdlog k(n) nee] which approximates !(G) within a factor of
k(n) for all graphs G with n vertices.
The lemma is stated for the maximum clique size problem, but it obviously holds for any
NP-optimization problem where the solution is an integer ranging from 1 to n. Note that it
does not matter if k(n) is not an integer, because checking whether !(G) is greater than x
is still an NP question when x is a fractional number. Once we have determined that !(G)
is contained in the interval (k(n) i ; k(n) i+1 ], we can output dk(n) i e as an approximation to
!(G). Also, if we drop the ceilings from our notation, then we can derive more readable
upper bounds on the complexity of approximating !(G) for some common approximation
factors (see Table 1).
The binary search strategy used to find the approximation to !(G) may seem naive.
However, we shall see later that the upper bounds differ from the lower bounds by at most an
additive constant. In any case, we can improve the upper bounds if there exists a polynomial
time algorithm which gives an approximate solution within a factor of f(n). Then, our
strategy is to first use the polynomial time algorithm to obtain an approximation x. We
know that the solution is between x and x \Delta f(n). Now, to find an approximation that is
within a factor of k(n), we divide the numbers from x to x \Delta f(n) into intervals:
x
In this case, the number of intervals is
l
log k(n) f(n)
, and we have the lemma:
Lemma 5 Let k(n) be a polynomial time computable function such that 1
Suppose that there exists a polynomial time algorithm which approximates !(G) within a
factor of f(n). Then there exists a function in PF SAT [dlogdlog k(n) f(n)ee] which approximates
within a factor of k(n) for all graphs G with n vertices.
Again, we note that this lemma applies to any NP-optimization problem whose solutions
range from 1 to n. This lemma may seem somewhat useless since the best known polynomial
time algorithm can only approximate the size of the maximum clique within a factor of
O(n=(log n) 2 ) [BH92]. If we were to use the new strategy outlined above, we would reduce the
number of queries needed to find a factor 2 approximation of !(G) to log(log
which would save us at most one query for various values of n. However, the following
corollary of the lemma does allow us to gauge the quality of our lower bound results.
Corollary 6 If no function in PF SAT [log log k(n) n\Gammalog 1=ffi ] approximates !(G) within a factor
of k(n), then no polynomial time algorithm can approximate !(G) within a factor of n ffi .
Corollary 6 gives us a natural interpretation of the difference between the upper bound
of log log k(n) n in Lemma 4 and the lower bound of log log k(n) \Gamma log 1=ffl (Theorem 15). This
difference of log 1=ffl reflects the fact that we do not know if there exists a polynomial time algorithm
which approximates !(G) within a factor of n ffi for 1. Thus, an improvement
of either the upper or the lower bound is possible.
Moreover, the observations about Lemma 5 are most useful when they are applied to
NP-optimization problems such as Set Cover. In the Set Cover problem we are given a finite
collection C of subsets of ng and asked to find the size of the smallest subcollection
ng. Since the size of the smallest set cover can be approximated
within a factor we have the following lemma:
Lemma 7 Let k(n) be a polynomial time computable function such that 1
Then there exists a function in PF SAT [dlogdlog k(n) (ln n+1)ee] which approximates the size of the
minimum set cover within a factor of k(n).
Now, by comparing Lemma 4 against Lemma 7, we can obtain a quantitative difference
between the complexity of approximating !(G) and the complexity of approximating the size
of the minimum set cover - not just a qualitative difference. For example, if we are allowed
to make log log(ln queries to SAT, then we can approximate the minimum set cover
within a factor of 2. However, using the same number of queries, we can only approximate
within a factor of n 1= log(ln n+1) . Thus, we can conclude that approximating set cover
within a factor of 2 has about the same complexity as approximating !(G) within a factor
of n 1= log(ln n+1) . Such a comparison is only possible by taking a quantitative view of the
complexity of approximations in terms of the number of queries.
Note that the existence of a "good" polynomial time approximation algorithm for a
problem has a greater effect on the complexity of approximating the problem than on the
complexity of finding the exact solution. For example, suppose that we have some NP-
optimization problem where the solution ranges from 1 to n. Without the help of an approximation
algorithm, we would need log n queries to find the exact solution and log log n
queries to find a factor 2 approximation. Now, suppose that we are given a polynomial time
algorithm that guarantees a factor 4 approximation. To find the exact solution we would
still need log(n queries. However, we only need one query (log log
to approximate within a factor of 2.
The upper bounds proven in this section uses a naive binary search strategy to determine
an interval that contains the optimal solution. One might suspect that a more clever
algorithm could use substantially fewer queries to the oracle. In the rest of the paper, we
show that unless some intractability assumption is violated (e.g.,
no polynomial time algorithm can reduce the number of queries by more than an additive
constant. These results give us relative lower bounds on the number of queries needed to approximate
the maximum clique size of a graph. We are also able to extend these techniques
to determine the query complexity of approximating the chromatic number of a graph and
the minimum set cover.
4 Lower bounds
4.1 Promise Problems and clique arithmetic
To prove our lower bound results, we need to introduce some more definitions and notations.
be the number of formulas in fF which
are satisfiable. I.e., # SAT
Definition 9 Let r(t) be a polynomially bounded polynomial time function. We define P r(t)
to be the following promise problem. Given a sequence of Boolean formulas F
where each F i has t variables and the promise that for all
Technically the size of the input to the promise problem is jF j. This size is
O(tr(t)) when the Boolean formulas are restricted to ones where each variable occurs only
a constant number of times. To simplify our notation, in the following lemma we count the
queries as a function of t rather than jF j. The following lemma provides a tight
lower bound on the complexity of P r and can be proven using the self-reducibility of SAT
and a tree pruning technique [HN93]. We include the proof for the sake of completeness.
r(t) be a logarithmically bounded polynomial time computable function. If
there exists an oracle X such that some polynomial time function solves P r(t) using fewer
than queries to X, then
Proof: Let be a polynomial time oracle Turing machine
which solves P r using q(t) queries to X. We know that log n), so the entire
oracle computation tree of M on input F polynomially bounded and can be
searched deterministically. In fact, the oracle computation tree has at most r(t) leaves,
since for all x, 2 dlog xe ! 2x. One of these leaves represents the correct computation of
contains the value of # SAT
However, there are r(t)
possible answers for # SAT
ranging from 0 to r(t). So, one possible answer, call
it z, does not appear in any leaf. Moreover, one of the leaves contains the correct answer,
so z 6= # SAT
Thus, we can construct a polynomial time Turing machine M 0
which on input F prints out a number z  r(t) such that z 6= # SAT
Now we show that Given a Boolean formula F , consider
its disjunctive self-reduction tree. Each node in the tree is a formula; the children of a node
are the two formulas obtained by instantiating one of the variables in the formula by 0 and
by 1. With F at the root of the tree, the tree has height t and exponential size. However,
we will only examine r(t) levels of the tree at a time. Now, let r(t) be a path
in this tree. Suppose that F i+1 2 SAT . Since F i+1 is a child of F i , we can assume that
. Thus, the promise condition of P r(t) holds and we can use M 0 to find a number
z, such that z 6= # SAT
replace the subtree rooted at F z with the subtree
rooted at F z+1 . If F z 62 SAT , then F z+1 62 SAT by the promise condition. If F z 2 SAT and
F z+1 62 SAT , then z would equal # SAT
our construction of
. Thus, F z+1 2 SAT iff F z 2 SAT and we have shortened the path by 1. Repeat this
process for all paths in any order until all the paths in the tree have length less than r(t).
Now, the original formula F is satisfiable iff one of the leaves (in which all the variables have
been instantiated) evaluates to true. Since the final tree is polynomially bounded, we can
check every leaf exhaustively. 2
In the proofs that follow we need to construct graphs in which the maximum clique size
can occur only at restricted intervals. To assist in this construction, we define two operators
on graphs: \Phi
and\Omega . We also use K i to denote the complete graph with i vertices.
Definition 11 Given two graphs G 1 and G 2 , the graph is constructed by
taking the disjoint union of the vertices of G 1 and G 2 . The edges of H are all the edges of
G 1 and G 2 , plus the edges (u; v) for each vertex u in G 1 and v in G 2 . (So, every vertex in
G 1 is connected to every vertex in G 2 ).
Given two graphs G 1 and G 2 , the graph
is constructed by
replacing each vertex of G 1 with a copy of G 2 . Furthermore, for each edge (u; v) in G 1 , each
vertex in the copy of G 2 replacing u is connected to every vertex in the copy of G 2 replacing
v. Note
that\Omega is not commutative and that we
higher precedence than \Phi .
Lemma 13 Let G 1 and G 2 be any two graphs, then
4.2 A simple lower bound
As a first lower bound result, we show that for all oracles X, no function in PF X[1] can
approximate !(G) within a factor of 2 unless . To do this, we start with the
assumption that some function f 2 PF X[1] does approximate !(G) within a factor of 2 and
show that using this function we can solve the promise problem P 2 using only one query to
X. Then,
In our construction, we start with the input to the promise problem P 2 , which is a pair of
Boolean formulas F 1 and F 2 each with t variables. Now using the reduction from Lemma 2,
we construct two graphs G 1 and G 2 with t d vertices such that
that t is sufficiently large so that t b ? 6
Consider the effect of the satisfiability of F 1 and F 2 on !(H). If F 1 62 SAT and F 2 62 SAT ,
then
1 This is identical to graph composition in Garey and Johnson. The cover of Garey and Johnson is the
picture of a 3-clique composed with a graph that has three points connected by 2 edges.
On the other hand, if Finally, if
Because of the promise condition of the promise problem, we do not have the case where
This restricts the value of !(H) to 3 non-overlapping intervals. In
these intervals are separated by a factor of 2. Thus, a factor of 2 approximation of !(H)
will tell us which formulas are satisfiable. For example, if we are given an approximation x
guaranteed to be within a factor of 2, and x  1:5 \Delta t b , then we know that both F 1 and F 2
are satisfiable. If this approximation can be achieved using only one query to X, then we
can solve the promise problem P 2 in PF X [1] and
4.3 The general construction
In this section we prove the general theorem for the lower bound on approximating the size
of the maximum clique in a graph. First, we define a class of approximation factors.
Definition 14 We call a function k : N ! R a nice approximation factor if it is computable
in polynomial time and all of the following hold:
1. 9n
2. 9n
3.
log m
log k(m)
log n
log k(n)
Please note that k(n) is nice if k(n) equals n 1=a , log n, (log n) a , or a constant  2.
The natural interpretation of the third condition is the following. Consider the function
k(n)). The function f(n) is also related to k(n) by: . The
third condition is satisfied if f(n) is increasing, if f(n) is constant or if f(n) is decreasing
but converges to a limit (e.g., when
by 1. Thus, if f(n) is decreasing almost everywhere, it must converge to a limit. Hence, the
third condition is not satisfied only when f(n) alternates between increasing and decreasing
infinitely often. We rule out these functions as approximation factors.
Theorem 15 Let k(n) be a nice approximation factor which is (1) unbounded, (2) converges
to an integral constant or (3) converges to a sufficiently large constant. Then, for all oracles
X, no polynomial time function can approximate !(G) within a factor of k(n) using
log log k(n)
or fewer queries to X unless log(1=ffl).
Proof: The general strategy of this proof is to reduce the promise problem P r to the
problem of approximating the maximum clique size of a graph H within a factor of k(n).
provides us with a lower bound on the complexity of P r (assuming that
a lower bound on the complexity of approximating !(H).
So, we begin with the input to the promise problem P r , the Boolean formulas, F
each with t variables. (The actual value of r will be chosen later.) We convert each formula
into a graph G i with vertices according to the construction described in Lemma 2.
The values of !(G i ) are restricted by:
Then we choose a gap size g. In the simple example above, g is 2. In this proof, the value
of g and r will depend on t. However, for notational convenience, we do not make this
dependency explicit. Moreover, we can only choose g to be a whole number. Now, given the
choices of r and g, we construct the graph H as follows:
At first glance, this does not appear to be a polynomial time construction because we could
double the size of each succeeding graph. However, r will turn out to be logarithmically
bounded, so jHj will be polynomially bounded. Finally, let
Now suppose there exists a polynomial time function which approximates !(H) within
a factor of k(n) using log log k(n) queries to X. We want to show that the factor k(n)
approximation of !(H) also tells us the value of # SAT
Also, we want to constrain
the choice of g and r so that log log k(n) being able
to approximate !(H) within a k(n) factor using only log log k(n) queries to X would
imply that To make this claim our choices of g and r are critical. We have already
encountered one constraint on g and r. The other constraints arise when we analyze the
possible values of !(H).
For the moment, assume that there are exactly z satisfiable formulas in F
are in SAT and F are in SAT by the promise condition of P r . We can
calculate !(H) as follows:
r
we can estimate the size of the second term by
Then, we can bound the size of the maximum clique of H:
We want to show that an approximation of !(H) within a factor of g will also allow
us to calculate # SAT
assume that we are provided with a function which
approximates !(H) within a factor g. To distinguish the case where z formulas are satisfiable
from the case where z are satisfiable, we must have:
That is, the upper bound on !(H) when z formulas are satisfiable must be smaller, by
a factor of g, than the lower bound on !(H) when z are satisfiable. Since
condition is satisfied if we have the constraint that g r t s ! t b . Similarly,
under this constraint we would also have: g( . Hence, we have restricted
the possible values of !(H) to r disjoint intervals which are separated by a factor of g.
Thus, given a number x which is guaranteed to be an approximation of !(H) within a factor
of k(n), k(n)  g, we can find the largest z such that gx   z t b . This largest z is equal to
It is important to note here that the approximation factor k(n) depends
on n which is the size of H and not the size of the original input. Furthermore, the value of
n depends on the value of g. Thus, it is not a simple task to choose g and have k(n)  g.
(Recall that
In summary, we must choose g and r such that the following constraints hold. (Recall
that we use g and g(t) interchangeably.)
Constraint 1: g(t) r
Constraint 2: k(n)  g(t).
Constraint 3:
(log log k(n) n) \Gamma c
The main difficulty of this proof is to choose the correct values for the parameters. For
example, we can satisfy Constraint 3 by picking a large value for r. However, if r is large,
then Constraint 1 is harder to satisfy. We also satisfy Constraint 2 easily by choosing a
large g, but a large g would force us to pick a small r which then violates Constraint 3. Let
We will show that the following choices satisfy the constraints.
l
log g
Note that g and r are chosen to be integers. This is important for our construction, but
it is also the source of some difficulties in our calculations. The reader may find the proof
easier to follow by substituting 2 or
for g. These are the two extreme possibilities.
First we show that Constraint 1 holds. By our choice of r, r  log g (t b\Gammas (g \Gamma 1)=g). By
removing the log g , isolating t b and using the fact that g r r , we obtain the following
and hence Constraint 1 holds.
We can also use Equation 1 to estimate n in terms of t. From our construction, we know
that From Equation 1, we know that  r ! t b\Gammas . Hence,
is a nice approximation factor, it is monotonic after some point. Hence, for large enough t,
holds.
Finally, we have to show that Constraint 3 holds. Since
It suffices to show that (log log k(n) n) 1), or that (ffl=2) log k(n) 1. By
substituting the definition of r, and being careful with the floor notation, we can satisfy
Constraint 3 by showingffl
log g
log k(n) n !ffl
log
In the next step, we rewrite (2=ffl) as follows. Recall that
log
log
log
ffl must be less than 1, (3
Constraint 3 by showing the following two inequalities:ffl
log g
log
log
log
Equation 3 holds since g=(g \Gamma 1) is bounded by 2 and n
Now, we have to show that Equation 4 holds. First, pick enough so that
Recall that
log
log dk(n
Consider the ratio: log k(n 0 )= log dk(n 0 )e. If k(x) is always an integer, then the ratio is just 1.
If k(x) is growing monotonically, then the ratio converges to 1 from below and will eventually
rise above the constant 1=(1+ ffi). In fact, it is sufficient to assume that k(x) is an unbounded
function. The proof also works when k(x) converges to an integral constant or a sufficiently
large constant. The proof does not work when k(x) is a small fractional constant (e.g., 2.5).
Hence, we exclude this case in the hypothesis of the theorem. (In that case, however, we can
prove the same theorem with which results in a worse lower bound.) Thus,
we may assume that for sufficiently large t
log
log
log
Using the third niceness property of k(x), for sufficiently large t
log
log
log n
log k(n)
log k(n) n:
Thus, Equations 3 and 4 are true, and all of the constraints are satisfied for large enough t.In the preceding theorem, we make some additional assumptions about k(n) beyond
niceness to show that Equation 4 holds. If we are willing to settle for a slightly worse lower
bound, we can prove a similar result for all nice approximation functions k(n). Alternatively,
we can make the assumption that ffl  1=4. The proofs for each case is nearly identical to the
proof of Theorem 15 except we use the fact that the ratio log k(n 0 )= log dk(n 0 )e is bounded
below by log 2= log 3  0:6309 since k(n)  2 for all n.
Corollary Let k(n) be a nice approximation factor. Then, for all oracles X, no polynomial
time function can approximate !(G) within a factor of k(n) using
log log k(n)
or
fewer queries to X unless log(1=ffl).
Corollary 17 Let k(n) be a nice approximation factor. If ffl  1=4, then for all oracles
X, no polynomial time function can approximate !(G) within a factor of k(n) using
log log k(n)
or fewer queries to X unless log(1=ffl).
5 Approximating the chromatic number
The results that we have stated so far also hold for many other NP-optimization problems.
For any NP-optimization problem where the solutions range from 1 to n (or even n a ), the
upper bound on the number of queries needed to approximate the problem can be derived
easily from the techniques in Section 3. To show that the lower bounds hold we need a
reduction from SAT to the new problem similar to the one for Clique in Lemma 2. Recently,
Lund and Yannakakis have discovered such reductions for Graph Coloring and some related
problems [LY94]. To repeat the proof, special attention must be given to any differences that
may arise between minimization and maximization (see Section 7). Thus, we could obtain
results analogous to the ones in Theorem 15 for the problem of approximating the chromatic
number of a graph.
In this section we take an alternative approach and prove the lower bounds using an
approximation preserving reduction from the maximum clique size problem to the chromatic
number of a graph [LY94]. However, this reduction increases the size of the graphs, so the
proof does not produce the best lower bounds. This approach can be extended to most of
the problems which Lund and Yannakakis show to have approximability properties similar
to that of Graph Coloring. We can show that Clique Partition, Clique Cover and Biclique
Cover have similar lower bounds. This follows from approximation preserving reductions
due to Simon [Sim90] for Clique Cover and Biclique Cover. These reductions preserve the
approximation ratio within 1+ ffl for any ffl ? 0 where the new problems have size n O(1=ffl) . On
the other hand, we have not been able to obtain a similar result for Fractional Chromatic
Number. The reason is that the reduction there only preserves the approximation ratio with
a log n multiplicative factor.
In the following, let ff(G) and (G) denote, respectively, the size of the largest independent
set and the chromatic number of a graph G. The next lemma is an application of the
results of Lund and Yannakakis.
Lemma There exists a polynomial time transformation T (G) such that for all graphs G
with n vertices and for all primes p, with n  p  2n, has the property that
Furthermore
Proof: By Proposition 4.1 2 in the appendix of Lund-Yannakakis [LY94], there exists a
polynomial time transformation T 0 (G; p; r) such that if G is a graph, p is a prime, r is a
r
Given a graph G on n vertices we define T as follows. Let find a prime p such
that n  p  2n (such primes exist by Bertrand's Theorem and can be found easily since
the length of the input is n not log n). Let T
:The following theorem shows that we can derive a lower bound on the complexity of
approximating the chromatic number of a graph using the lemma above.
Theorem 19 Let k(n) be a nice approximation factor such that for large n,
Then for all oracles X no polynomial time function can approximate (G) within a factor of
using
log log k(n)
or fewer queries to X unless
Proof: We reduce approximating the clique size of a graph Q to approximating the chromatic
number of a graph H. If (H) can be approximated using too few queries, then the
lower bound on approximating !(Q) from Corollary 16 would be violated and we can conclude
that
We are given a nice approximation factor k(n). Suppose that some polynomial time
algorithm A(G) approximates (G) within a factor of k(n) using
log log k(n)
queries
to X for all graphs G with n vertices. Let k 0 It is simple to check that 2k 0 (n) is
also a nice approximation factor.
Proposition 4.1 as stated by Lund and Yannakakis requires that p ? r but the proofs show in fact that
are sufficient. We use this proposition instead of their main theorem because it deals with
general graphs instead of the special graphs produced by the reduction in Lemma 2.
given any graph Q with n vertices, we approximate !(Q) within a factor of 2k 0 (n)
as follows. Construct using Lemma 18, where Q 0 is the complement of Q. So,
we know that ff(Q 0 we construct the graph H by adding
dummy vertices to H 0 so that Finally, we use the
algorithm A to compute an approximation of (H) within a factor of k(N ). This uses no
more than
log log k(N)
log log
queries to X. Since A(H) is a factor k(N) approximation, we know
From Lemma 18, we also know that
Thus, the value p 3 n 2 =A(H) approximates !(Q) within a factor of
Since 2k 0 (n) is a nice approximation factor, by Corollary 16, approximating !(Q) within
has a lower bound of
log log 2k 0 (n)
log log
Finally, since (log log k(n 8 computing A(H) used no more than
log log 2k 0 (n)
queries to X. Thus, if such an algorithm exists, decreases the lower bound of Corollary 16 by 4 queries. This decrease is
due in part to the fact that jHj  jQj 7 . Thus, a more efficient reduction from clique size
to chromatic number would yield a tighter lower bound. Also, for specific approximation
especially where the relationship between k(n) and k(n 7 ) is explicit, we can obtain
slightly better lower bounds by reproducing the proof of Theorem 15.
6 The value of ffl
The lower bound results in the preceding sections depend on the value of the constant ffl,
1. Recall that this is the same ffl used by Arora et al. to show no polynomial
time algorithm can approximate !(G) within a factor of n ffl unless . Note that a
larger value of ffl indicates a better non-approximability result which in turn provides tighter
upper and lower bounds in the results of previous sections. Also, recall that for bounded
query classes even an improvement of one query is significant.
Currently, the exact value of ffl is not known. However, by weakening the assumption that
to BPP 6= NP , Bellare, Goldwasser, Lund and Russell [BGLR93] have shown that
no polynomial time algorithm can approximate !(G) within a factor of n 1=30\Gammao(1) . A further
improvement was made by Bellare and Sudan [BS94] who showed that no polynomial time
algorithm can approximate !(G) within a factor of n 1=5\Gammao(1) unless . In this
section, we use these results to obtain explicit lower bounds on the number of queries needed
to approximate !(G) under the stronger assumption that RP 6= NP .
To prove these lower bound results, we need to adapt the proof techniques of the previous
section to work with randomized functions instead of deterministic functions. A naive
approach would use a straightforward modification of Lemma 2 to produce a randomized
reduction f from SAT to Clique Size such that:
The difficulty with this approach is that the randomized version of Lemma 10 will use this
randomized reduction polynomially many times. Thus, when we show that if the
lower bounds are violated, we have to be very careful with the value of ffi to make certain that
the success probability of the overall procedure remains high enough. Such detailed analysis
is possible using the techniques developed by Rohatgi [Roh92]. However, the analysis can
be made much simpler by observing that the randomized reduction from SAT to Clique Size
can be achieved with "uniform" probability - that is, the same random string z can be used
to correctly reduce any instance of SAT of a certain length. In the following, let jF j denote
the length of the encoding of the Boolean formula F .
Lemma 20 There exist constants s, b and d, with
and a deterministic polynomial time function f such that
where for each Boolean formula F , jF t, and each random string z  p(t), f(F; z)
produces a graph with t d vertices.
Proof This reduction is implicit in the work of Zuckerman [Zuc93], we include a
proof sketch for completeness. In this proof, the reduction f constructs a graph G from the
formula F and a random string z. The random string z is used to choose a disperser graph
H which allows f to amplify probability bounds. Choosing this disperser is the only random
step used by f . If the randomly chosen H is indeed a disperser, then the same H can be
used to reduce any formula F with t variables to a graph G. Hence, the success probability
of the reduction is independent of the particular formula F .
The starting point of the proof is not the deterministic reduction in Lemma 2, but the
probabilistically checkable proof for SAT. As reported by Arora et al., there is a probabilistically
checkable proof for SAT where the verifier V uses c 1 log n random bits and looks at
bits of the proof such that
accepts
F 62 SAT =) 8; P rob z2f0;1g c 1 log n[V
From the verifier V and the input F with t variables, we can use the construction of Feige,
Goldwasser et al. [FGL + 91] to construct a graph G such that
In this construction, each vertex of G represents one computation path of the verifier V (for
every possible random string and every sequence of answer bits from the proof). An edge is
added between two vertices, if some proof  contains the answer bits which agree with both
computation paths.
The construction above gives an approximation "gap" of only 1=2. To obtain better re-
sults, we have to decrease the probability that V accepts an incorrect proof when F 62 SAT
without using too many additional random bits. This decrease can be achieved deterministically
[CW89], which leads to Lemma 2, but then we lose track of the values of b, s and
d. Alternatively, as Zuckerman [Zuc93] pointed out, we can decrease the verifier's error
randomly.
The key idea to Zuckerman's construction is to use special graphs called dispersers which
were first introduced by Sipser [Sip86]. For our purposes, a disperser may be defined as
a bipartite graph with t c 3 vertices on the left and t c 1 vertices on the right such that each
left vertex has degree and every set of t c 1 left vertices is connected to at
least t c 1 =2 right vertices. The value of the constant c 3 will be chosen later. By a theorem
which Zuckerman attributes to Sipser [Zuc93, Theorem 3], such a disperser can be randomly
generated with probability by choosing the D neighbors of each left vertex randomly.
Suppose that we have a disperser H. We use H to construct a new verifier V 0 . We
interpret each left vertex of H as a random string for V 0 and each right vertex of H as
a random string for V . V 0 simulates V by randomly choosing a left vertex of H. This
uses c 3 log t random bits. Let z z D be the right vertices connected to the chosen left
vertex. times using each of z as the random string for V . If every
simulation of V accepts the proof , then V 0 accepts the proof . The complete simulation
uses c 3 log t random bits and looks at Dc 2 bits of the proof.
Clearly, if F 2 SAT , then V 0 will always accept. In fact, V 0 will accept even when H
does not have the desired properties. Conversely, consider the case when F 62 SAT . We
want to show that V 0 accepts with probability less than t c 1 =t c 3 . So, suppose that V 0 accepted
with probability  t c 1 =t c 3 . Then, t c 1 of the left vertices cause V 0 to accept. Thus, all the
right vertices connected to these left vertices must cause V to accept. Since H is a disperser
with the properties mentioned above, at least t c 1 =2 right vertices must cause V to accept.
This contradicts our assumption about the error probability of V . Thus, when F 62 SAT ,
accepts a proof  with probability less than t c 1 =t c 3 .
Now we construct a graph G from V 0 as described above. Since V 0 uses c 3 log t random
bits and looks at Dc 2 bits of the proof, the graph G will have vertices. When
has a "big" clique of size t c 3 . When F 62 SAT , G has a "small" clique of size
no more than t c 1 . The ratio of the size of the "big" clique to the size of the "small" clique
expressed in terms of n is:
Substituting c 3 log
d
Thus, for all choosing c 3 to be large enough. Recall
that c 2 is the number of bits in the proof that the verifier reads. This calculation shows
the effect of c 2 on the value of ffl. Finally, observe that the only random step used in the
reduction is choosing the disperser H. 2
The results of Bellare, Goldwasser, Lund and Russell [BGLR93] can be used to show
that in Lemma 20 the ratio (b \Gamma produce a verifier for SAT
that uses only 29 bits of the proof and follow Zuckerman's construction as described above.
However, we are unable to exploit the results of Bellare and Sudan [BS94], because they use
randomness for sampling - not just to generate pseudo-random bits. Nevertheless, we can
give explicit lower bounds on the query complexity of approximating !(G).
Theorem 21 Let k(n) be a nice approximation factor. Then, for all oracles X, no polynomial
time function can approximate !(G) within a factor of k(n) using
log log k(n)
or
fewer queries to X unless
Proof To prove this theorem, we simply follow the proof of Theorem 15 except
that we use instead of Lemma 2 to reduce SAT to Clique Size.
Since the success probability of the reduction is independent of the formula F , repeated use
of the reduction does not decrease the success probability of the overall procedure. Again,
the only random step in the entire procedure is randomly choosing a disperser graph H. This
is also the case when we use the tree pruning procedure in Lemma 10 to look for a satisfying
assignment for the given Boolean formula. Since our procedure accepts a formula only when
a satisfying assignment is found, it will never accept an unsatisfiable formula. The procedure
may reject a satisfiable formula if the graph H turns out not to be a disperser. However,
the probability of this happening is small. Thus, the overall procedure is an RP algorithm
for SAT.
Finally, note that in Equation 2 of Theorem 15, we need to show
log g
log k(n) n !ffl
log
In this proof, the value of ffl is known, so we can rewrite the 2=ffl asffl
Then, as before,ffl
log g
because 2. Also, we do not need any additional assumptions on k(n) to show
log
log
log
log dk(n 0 )e
log
log
because log k(n 0 )= log dk(n 0 )e  log 2= log 3  0:6309. Hence, 1:8 \Delta log k(n 0 )= log dk(n 0 )e ? 1:1
and we can let 0:1. Thus, the assumption that k(n) is nice and
suffices. 2
Using the proof techniques described above we can also extend our results to lower bounds
for approximating the chromatic number.
Corollary 22 Let k(n) be a nice approximation factor such that for large n,
Then for all oracles X no polynomial time function can approximate (G) within a factor
of k(n) using
log log k(n)
or fewer queries to X unless
7 Lower bounds for set cover
An instance of the Set Cover problem is a set system such that for all i,
ng. We are asked to find the size of the smallest collection of S i which covers
ng. We denote the size of the minimum cover of S as SETCOVER(S).
As we have discussed in the section on upper bounds, the Set Cover problem has a
different complexity compared to Clique or Chromatic Number because there exist polynomial
time algorithms that approximate the size of the minimum set cover within a factor of
1. In this section we derive a lower bound on the complexity of approximating the
size of the minimum set covering in terms of the number of queries to SAT.
One difficulty arises when we apply our techniques to minimization problems. To illustrate
this, consider the construction of the graph H in Section 4.2. We use the reduction
from SAT to Clique to construct a graph G 1 from a formula F 1 . This reduction has the
special property that if F 1 2 SAT , then This equality is very important, because
it allows us to put only two copies of G 2 in H. If we only knew that !(G 1
could be as large as m. Thus, to ensure a large enough gap between the case where
SAT from the case where F 1 would have to use 2m=t b
copies of G 2 . This would make the graph H too big and produce very bad lower bounds in
the general theorem.
If equality is not possible, then we can settle for a good upper bound. For example, if
the reduction from SAT to Clique guaranteed that F 1 2 SAT =) t b
we only need to put 6 copies of G 2 in H. In the general case, we would obtain a lower bound
of log log 3k(n)
The reduction from SAT to Set Cover in [LY94] does not give an upper bound on the
size of the minimum set cover when the original formula is unsatisfiable. Thus, we must use
the following lemma and theorem.
Lemma There exists a constant CONST such that for all l; m  CONST where l  m and
log there exist a set B and subsets C
1. For any sequence of indices 1  collection
covers B where D i j
is either C
or the complement of C
2. do cover B.
3.
Furthermore, there exists a probabilistic Turing Machine which, on input l; m (in binary)
produces such a set system with probability 2=3.
g. Let the subsets C Cm be a collection of
subsets of B chosen randomly and independently - i.e., for each x 2 B and each C i , x 2 C i
with probability one half. We show that with probability over 2=3 this collection suffices. Fix
as in the statement of the lemma. The probability that
is . The number of different D i j
's is at most 2 l
l
. Thus the probability that
some collection of D i 1
covers B is bounded by
l
Hence the probability that item 1 occurs is at least 5=6.
Secondly, note that the probability that the first 1:1l sets cover B is
using the fact that (1 \Gamma x)  e \Gamma2x for x 2 [0; 1=2]. We need this quantity to be greater than
Hence we need
log
Since log holds for large enough l and m. Therefore, the desired constant
CONST can be found. Hence the probability of satisfying item 2 is at least 5=6. Since the
probability of satisfying item 1 is  5=6 and the probability of satisfying item 2 is  5=6,
the probability of satisfying both is at least 2=3. 2
Theorem 24 Given a formula ', let S ' be the instance of Set Cover described below. Let
N be the size of S ' . Then, there exists an integer K (depending only on the size of ') such
that,
0:99Klog N  SETCOVER(S ' )
1:1Klog
where the last property holds with probability at least 2=3. Furthermore, the reduction can
be applied to any number of formulas ' of the same size, and with probability 2/3, all the
instances of Set Cover obtained will have the property above.
Proof: The proof of this theorem is a modification of the construction by Lund and
Yannakakis [LY94]. In the rest of this proof we assume that the reader is familiar with
the notation and the proof in [LY94]. Given a formula ', we carry out the construction in
Section 3.1 of [LY94] except that we use the sets B;C as specified in Lemma 23 as
our building blocks. Using the ideas in [LY94] we obtain:
1.
2. ' 62 SAT implies SETCOV ER(S ' )
since the first 1:1l answers for every query in Q 2 cover all the points, by
Lemma 23. Then, since jQ 1
Now the theorem follows since l can be chosen such that log N for any ffl ? 0.
Also, note that thus we can apply Lemma 23.
Furthermore, note that once we have chosen one set system from Lemma 23, we can use
it in any number of reductions involving instances of the same size. Thus if the set system
has the required property then all the reduced instances will have the required properties.The consequence of this theorem is that there exists a randomized reduction from SAT
to Set Cover which runs in time O(n polylog n ). This reduction allows us to duplicate the
construction of Theorem 15 for Set Cover and obtain the following lower bound.
Theorem R be a function such that for all n large enough, 2  k(n) ! n;
implies that
log log m
log k(m)
log log n
log k(n)
Let S be an instance of Set Cover. Then, for all oracles X, no polynomial time function can
approximate the size of the minimum set cover within a factor of k(n) using log log k(n)
or fewer queries to X unless NP ' RT IME[n polylog n ].
Proof: This proof is analogous to the proof of Theorem 21. We start with the promise
problem P r , with r to be chosen later. Since our construction is in time O(n polylog n ), we need
a different lower bound on the complexity of P r . Using the proof technique of Lemma 10,
one can show that for using
fewer than dlog(r 1)e queries to any oracle X, then NP ' DT IME[n polylog n ]. As in
Theorem 21, it is important that in Theorem 24 the randomized reduction from SAT to
Set Cover can be used repeatedly without decreasing the success probability of the overall
procedure.
r be a sequence of Boolean formulas with t variables each which satisfies
the promise condition of the promise problem P r . We use Theorem 24 to construct r instances
of Set Cover S be the size of the underlying set of S i . Since the construction
takes time O(n polylog n ), m is O(t polylog t ). We know with probability 2=3 that for each i:
1:1Klog m:
We will now restrict our attention to this case. We combine the r instances of Set Cover
into a single instance of Set Cover
Let n be the size of the underlying set for T . We define \Phi
and\Omega so that
and for any positive integer a
This is accomplished as follows. Let
two instances of Set Cover. We define S 1 \Phi S 2 to be (n 1
g. Then we can define
simply as S \Phi repeated
a times.
As in the proof of Theorem 15, the value of g in the construction of T will be chosen
later. Note that we construct T using g r\Gamma1 copies of S 1 instead of g r\Gamma1 copies of S r . This
is "backwards" compared to the construction H in Theorem 15. We need to make this
change because SETCOVER(S i ) is small when F i 2 SAT and large when F i 62 SAT .
(Again, backwards compared to Clique.) Then, a good approximation of SETCOV ER(T )
will solve the promise problem P r . However, here the approximation must be within a factor
of 0:9g instead of g because we only know that SETCOV ER(S i ) is in the interval between
log m and 1:1K log m when F i 62 SAT .
In this construction, when there are exactly z satisfiable formulas in F
the following bounds:
1:1
Thus, we can obtain a lower bound for approximating the size of the minimum set cover
(assuming NP 6' RT IME[n polylog n ]) if we show that there exist r and g which satisfy the
following constraints. Recall that m and n are the sizes of the underlying sets for S and T
respectively. The value of m is expressible in terms of t. To make our notation simpler, we
express g and r in terms of m instead of t or drop the argument altogether.
Constraint 1: g(m) r ! 1:1log m.
Constraint 2: k(n)  0:9g(m).
Constraint 3:
log log k(n)
For this proof, we let n choose g and r as follows:
log g
As in the proof of Theorem 15, our choice of r implies that Constraint 1 holds and that
non-decreasing almost everywhere, it follows that k(n)  0:9g(m) and
that Constraint 2 also holds.
Finally, we show that Constraint 3 holds. It suffices to show that the following equations
hold. (They are analogous to Equations 3 and 4 in Theorem 15.)
log k(n)
Equation 5 is satisfied for m large since g  2, 2. Equation 6 is proved as follows.
We start with the "niceness" assumptions on k(n) and obtain
log k(n) ln n
log log n
log k(n)
log log n 0
log
Recall that n m. Then for large m, (log m) 1:1 . Thus, we have:
log log n 0
log
log log m
log
Then, using the fact that for x  2, log 3 \Delta log x= logdx=0:9e ? 1, we have:
1:1 \Delta log log m
log
log
logdk(n 0 )=0:9e
log g
log 3  0:005. Also, we know that for m large
enough, 0:005 log log m ? 1:75 \Delta log(2=1:1). Therefore,
log g
log g
Therefore, Equation 6 holds and we have completed the proof. 2
Updates
Since the original submission of this paper, additional connections between bounded query
classes and NP-approximation problems have been discovered. Chang [Cha94a] showed
that approximating clique size is actually complete for certain bounded query classes. This
completeness produces reductions between NP-approximation problems (e.g., from approximating
the chromatic number to approximating clique size). In addition, bounded query
classes can also be used to measure the difficulty of finding the vertices of an approximate
clique, not just its size [Cha94b]. Also, Crescenzi, Kann, Silvestri and Trevisan [CKST95]
have shown that finding the vertices of the largest clique cannot be reduced to finding the
vertices of an approximate clique unless the Polynomial Hierarchy collapses. Bounded query
classes have also been used to measure the hardness of optimization problems [CT94] and
to compare various kinds of approximation preserving reductions [CKST95].

Acknowledgements

The authors would like to thank Richard Beigel and Suresh Chari for many helpful discus-
sions. Thanks also go to Samir Khuller, Martin Kummer and Frank Stephan for proofreading
drafts of this paper.



--R

Some connections between bounded query classes and non-uniform complexity
Polynomial terse sets.
Proof verification and hardness of approximation problems.
Probabilistic checking of proofs.
A structural theorem that depends quantitatively on the complexity of SAT.
Bounded queries to SAT and the Boolean hierarchy.

Efficient probabilistically checkable proofs and applications to approximations.
Approximating maximum independent sets by excluding subgraphs.
Improved non-approximability results
On the query complexity of clique size and maximum satisfiability.
Structural complexity column: A machine model for NP-approxima- tion problems and the revenge of the Boolean hierarchy
The Boolean hierarchy and the polynomial hierarchy: a closer connection.
Structure in approximation classes.
On approximation scheme preserving reducibility and its applications.

Approximating clique is almost NP-complete
Computers and Intractability: A Guide to the Theory of NP-Completeness


Approximation algorithms for combinatorial problems.
The complexity of optimization problems.
Algebraic methods for interactive proof systems.
On the ratio of optimal integral and fractional covers.
On the hardness of approximating minimization problems.
Saving queries with randomness.

On approximate solutions for combinatorial optimization problems.

More complicated questions about maxima and minima and some closures of NP.
On the Boolean closure of NP.

--TR

--CTR
Richard Chang, Bounded queries, approximations, and the Boolean hierarchy, Information and Computation, v.169 n.2, p.129-159, September 15, 2001
bounded queries;set cover;NP-completeness;maximum clique;chromatic number;approximation algorithm