Gadgets, Approximation, and Linear Programming.
We present a linear programming-based method for finding "gadgets," i.e., combinatorial structures reducing constraints of one optimization problem to constraints of another. A key step in this method is a simple observation which limits the search space to a  finite one. Using this new method we present a number of new, computer-constructed gadgets for several different reductions. This method also answers a question posed by Bellare, Goldreich, and Sudan [SIAM J.  Comput., 27 (1998), pp. 804--915] of how to prove the optimality of gadgets: linear programming duality gives such proofs.The new gadgets, when combined with recent results of H stad [ Proceedings of the 29th ACM Symposium on Theory of Computing, 1997, pp. 1--10], improve the known inapproximability results for MAX CUT and MAX DICUT, showing that approximating these problems to within factors of $16/17 + \epsilon$ and $12/13+ \epsilon,$ respectively, is NP-hard for every $\epsilon > 0$. Prior to this work, the best-known inapproximability thresholds for both problems were 71/72 (M. Bellare, O. Goldreich, and M. Sudan [ SIAM J. Comput., 27 (1998), pp. 804--915]). Without using the gadgets from this paper, the best possible hardness that would follow from Bellare, Goldreich, and Sudan and H{s}tad is $18/19$. We also use the gadgets to obtain an improved approximation algorithm for MAX3 SAT which guarantees an approximation ratio of .801. This improves upon the previous best bound (implicit from M. X. Goemans and D. P. Williamson [ J. ACM, 42 (1995), pp. 1115--1145]; U. Feige and M. X. Goemans [ Proceedings of the Third Israel Symposium on Theory of Computing and Systems, 1995, pp. 182--189]) of .7704.
Introduction
. A \gadget" is a nite combinatorial structure which translates
a given constraint of one optimization problem into a set of constraints of a
second optimization problem. A classical example is in the reduction from 3SAT to
MAX 2SAT, due to Garey, Johnson and Stockmeyer [6]. Given an instance of 3SAT
on variables X and with clauses C the reduction creates an instance
of MAX 2SAT on the original or \primary" variables along with
new or \auxiliary" variables Y . The clauses of the MAX 2SAT instance are
obtained by replacing each clause of length 3 in the 3SAT instance with a \gadget", in
this case a collection of ten 2SAT clauses. For example the clause C
would be replaced with the following ten clauses on the variables
new auxiliary variable Y
The property satised by this gadget is that for any assignment to the primary vari-
ables, if clause C k is satised, then 7 of the 10 new clauses can be satised by setting
only 6 of the 10 are satisable. (Notice that the gadget
An extended abstract of this paper appears in the Proceedings of the 37th IEEE Symposium on
Foundations of Computer Science, pages 617-626, Burlington, Vermont, 14-16 October 1996.
y Columbia University, Department of Computer Science, 1214 Amsterdam Avenue, New York,
NY 10027, USA. luca@cs.columbia.edu. Part of this work was done while the author was at the
University of Rome \La Sapienza" and visiting IBM Research.
z IBM T.J. Watson Research Center, P.O. Box 218, Yorktown Heights NY 10598. fsorkin,
dpwg@watson.ibm.com.
x MIT, Laboratory for Computer Science, 545 Technology Square, Cambridge, MA 02139, USA.
madhu@mit.edu. Work supported in part by an Alfred P. Sloan Foundation fellowship. Part of this
work was done while the author was at the IBM Thomas J. Watson Research Center.
L. TREVISAN, G. B. SORKIN, M. SUDAN, AND D. P. WILLIAMSON
associated with each clause C k uses its own auxiliary variable Y k , and thus Y k may
be set independently of the values of variables not appearing in C k 's gadget.) Using
this simple property of the gadget it is easy to see that the maximum number of
clauses satised in the MAX 2SAT instance by any assignment is 7m if and only if
the instance of 3SAT is satisable. This was used by [6] to prove the NP-hardness of
solving MAX 2SAT. We will revisit the 3SAT-to-2SAT reduction in Lemma 6.5.
Starting with the work of Karp [12], gadgets have played a fundamental role in
showing the hardness of optimization problems. They are the core of any reduction
between combinatorial problems, and they retain this role in the spate of new results
on the non-approximability of optimization problems.
Despite their importance, the construction of gadgets has always been a \black
art", with no general methods of construction known. In fact, until recently no one
had even proposed a concrete denition of a gadget; Bellare, Goldreich and Sudan [2]
nally did so, with a view to quantifying the role of gadgets in non-approximability
results. Their denition is accompanied by a seemingly natural \cost" measure for
a gadget. The more \costly" the gadget, the weaker the reduction. However, rstly,
nding a gadget for a given reduction remained an ad hoc task. Secondly, it remained
hard to prove that a gadget's cost was optimal.
This paper addresses these two issues. We show that for a large class of reductions,
the space of potential gadgets that need to be considered is actually nite. This
is not entirely trivial, and the proof depends on properties of the problem that is
being reduced to. However, the method is very general, and encompasses a large
number of problems. An immediate consequence of the niteness of the space is the
existence of a search procedure to nd an optimal gadget. But a naive search would be
impracticably slow, and search-based proofs of the optimality (or the non-existence)
of a gadget would be monstrously large.
Instead, we show how to express the search for a gadget as a linear program (LP)
whose constraints guarantee that the potential gadget is indeed valid, and whose
objective function is the cost of the gadget. Central to this step is the idea of working
with weighted versions of optimization problems rather than unweighted ones.
(Weighted versions result in LPs, while unweighted versions would result in integer
programs, IPs.) This seemingly helps only in showing hardness of weighted optimization
problems, but a result due to Crescenzi, Silvestri and Trevisan [3] shows that
for a large class of optimization problems (including all the ones considered in this
paper), the weighted versions are exactly as hard with respect to approximation as the
unweighted ones. Therefore, working with a weighted version is as good as working
with an unweighted one.
The LP representation has many benets. First, we are able to search for much
more complicated gadgets than is feasible manually. Second, we can use the theory
of LP duality to present short(er) proofs of optimality of gadgets and non-existence
of gadgets. Last, we can solve relaxed or constrained versions of the LP to obtain
upper and lower bounds on the cost of a gadget, which can be signicantly quicker
than solving the actual LP. Being careful in the relaxing/constraining process (and
with a bit of luck) we can often get the bounds to match, thereby producing optimal
gadgets with even greater e-ciency!
Armed with this tool for nding gadgets (and an RS/6000, OSL, and often
GADGETS, APPROXIMATION, AND LINEAR PROGRAMMING 3
some of the known gadgets and construct many new ones. (In
what follows we often talk of \gadgets reducing problem X to problem Y" when we
mean \gadgets used to construct a reduction from problem X to problem Y".) Bellare
et al. [2] presented gadgets reducing the computation of a \verier" for a PCP
(probabilistically checkable proof system) to several problems, including MAX 3SAT,
MAX 2SAT, and MAX CUT. We examine these in turn and show that the gadgets
in [2] for MAX 3SAT and MAX 2SAT are optimal, but their MAX CUT gadget is
not. We improve on the e-ciency of the last, thereby improving on the factor to
which approximating MAX CUT can be shown to be NP-hard. We also construct a
new gadget for the MAX DICUT problem, thereby strengthening the known bound
on its hardness. Plugging our gadget into the reduction (specically Lemma 4.15)
of [2], shows that approximating MAX CUT to within a factor of 60=61 is NP-hard,
as is approximating MAX DICUT to within a factor of 44=45. 2 For both problems,
the hardness factor proved in [2] was 71=72. The PCP machinery of [2] has since
been improved by Hastad [9]. Our gadgets and Hastad's result show that, for every
> 0, approximating MAX CUT to within a factor of 16=17 +  is NP-hard, as is
approximating MAX DICUT to within a factor of 12=13+ . Using Hastad's result in
combination with the gadgets of [2] would have given a hardness factor of
for both problems, for every  > 0.
Obtaining better reductions between problems can also yield improved approximation
algorithms (if the reduction goes the right way!). We illustrate this point by
constructing a gadget reducing MAX 3SAT to MAX 2SAT. Using this new reduction
in combination with a technique of Goemans and Williamson [7, 8] and the state-of-
the-art :931-approximation algorithm for MAX 2SAT due to Feige and Goemans [5]
(which improves upon the previous :878-approximation algorithm of [8]), we obtain
a :801-approximation algorithm for MAX 3SAT. The best result that could be obtained
previously, by combining the technique of [7, 8] and the bound of [5], was :7704.
(The best previously published result is a :769-approximation algorithm, due to Ono,
Hirata, and Asano [14].)
Finally, our reductions have implications for probabilistically checkable proof sys-
tems. Let PCP c;s [log; q] be the class of languages that admit membership proofs that
can be checked by a probabilistic verier that uses a logarithmic number of random
bits, reads at most q bits of the proof, accepts correct proofs of strings in the language
with probability at least c, and accepts purported proofs of strings not in the language
with probability at most s. We show: rst, for any  > 0, there exist constants
c and s, c=s > 10=9 , such that NP  PCP c;s [log; 2]; and second, for all c; s with
c=s > 2:7214, PCP c;s [log; 3]  P. The best bound for the former result obtainable
from [2, 9] is 22=21 ; the best previous bound for the latter was 4 [16].
All the gadgets we use are computer-constructed. In the nal section, we present
an example of a lower bound on the performance of a gadget. The bound is not
computer constructed and cannot be, by the nature of the problem. The bound still
relies on dening an LP that describes the optimal gadget, and extracting the lower
1 Respectively, an IBM RiscSystem/6000 workstation, the IBM Optimization Subroutine Library,
which includes a linear programming package, and (not that we are partisan) IBM's APL2 programming
language.
Approximation ratios in this paper for maximization problems are less than 1, and represent
the weight of the solution achievable by a polynomial time algorithm, divided by the weight of the
optimal solution. This matches the convention used in [18, 7, 8, 5] and is the reciprocal of the
measure used in [2].
4 L. TREVISAN, G. B. SORKIN, M. SUDAN, AND D. P. WILLIAMSON
bound from the LP's dual.
Subsequent work. Subsequent to the original presentation of this work [17], the
approximability results presented in this paper have been superseded. Karlo and
Zwick [10] present a 7/8-approximation algorithm for MAX 3SAT. This result is tight
unless NP=P [9]. The containment result PCP c;s [log; 3]  P has also been improved
by Zwick [19] and shown to hold for any c=s  2. This result is also tight, again
by [9]. Finally, the gadget construction methods of this paper have found at least
two more applications. Hastad [9] and Zwick [19] use gadgets constructed by these
techniques to show hardness results for two problems they consider, MAX 2LIN and
MAX NAE3SAT respectively.
Version. An extended abstract of this paper appeared as [17]. This version corrects
some errors, pointed out by Karlo and Zwick [11], from the extended abstract.
This version also presents inapproximability results resting on the improved PCP
constructions of Hastad [9], while mentioning the results that could be obtained otherwise

Organization of this paper. The next section introduces precise denitions which
formalize the preceding outline. Section 3 presents the niteness proof and the LP-based
search strategy. Section 4 contains negative (non-approximability) results and
the gadgets used to derive them. Section 5 brie
y describes our computer system
for generating gadgets. Section 6 presents the positive result for approximating
MAX 3SAT. Section 7 presents proofs of optimality of the gadgets for some problems
and lower bounds on the costs of others. It includes a mix of computer-generated and
hand-generated lower bounds.
2. Denitions. We begin with some denitions we will need before giving the
denition of a gadget from [2]. In what follows, for any positive integer n, let [n]
denote the set ng.
Definition 2.1. A (k-ary) constraint function is a boolean function f :
1g. We refer to k as the arity of a k-ary constraint function f . When
it is applied to variables X (see the following denitions) the function f is
thought of as imposing the constraint f(X
Definition 2.2. A constraint family F is a collection of constraint functions.
The arity of F is the maximum of the arity of the constraint functions in F .
Definition 2.3. A constraint C over a variable set
is a constraint function and are
distinct members of [n]. The constraint C is said to be satised by an assignment
an to X We say that
constraint C is from F if f 2 F .
Constraint functions, constraint families and constraints are of interest due to
their dening role in a variety of NP optimization problems.
Definition 2.4. For a nitely specied constraint family F , MAX F is the
optimization problem given by:
Input: An instance consisting of m constraints C
non-negative real weights w instance is thus a triple
w).)
Goal: Find an assignment ~ b to the variables ~
which maximizes the weight
of satised constraints.
Constraint functions, families and the class fMAX F j Fg allow descriptions of
GADGETS, APPROXIMATION, AND LINEAR PROGRAMMING 5
optimization problems and reductions in a uniform manner. For example, if
2SAT is the constraint family consisting of all constraint functions of arity at most
2 that can be expressed as the disjunction of up to 2 literals, then MAX 2SAT is
the corresponding MAX F problem. Similarly MAX 3SAT is the MAX F problem
dened using the constraint family consisting of all constraint functions of
arity up to 3 that can be expressed as the disjunction of up to 3 literals.
One of the motivations for this work is to understand the \approximability" of
many central optimization problems that can be expressed as MAX F problems,
including MAX 2SAT and MAX 3SAT. For  2 [0; 1], an algorithm A is said
to be a -approximation algorithm for the MAX F problem, if on every instance
w) of MAX F with n variables and m constraints, A outputs an assignment
~a s.t.
b)g. We say that the problem MAX F
is -approximable if there exists a polynomial time-bounded algorithm A that is a
-approximation algorithm for MAX F . We say that MAX F is hard to approximate
to within a factor  (-inapproximable), if the existence of a polynomial time
-approximation algorithm for MAX F implies NP=P.
Recent research has yielded a number of new approximability results for several
MAX F problems (cf. [7, 8]) and a number of new results yielding hardness of approximations
(cf. [2, 9]). One of our goals is to construct e-cient reductions between
MAX F problems that allow us to translate \approximability" and \inapproximabil-
ity" results. As we saw in the opening example such reductions may be constructed by
constructing \gadgets" reducing one constraint family to another. More specically,
the example shows how a reduction from 3SAT to 2SAT results from the availability,
for every constraint function f in the family 3SAT, of a gadget reducing f to the
family 2SAT. This notion of a gadget reducing a constraint function f to a constraint
family F is formalized in the following denition.
Definition 2.5 (Gadget [2]). For
f0; 1g, and a constraint family F : an -gadget (or \gadget with performance ")
reducing f to F is a set of variables Y collection of real weights
associated constraints C j from F over primary variables
and auxiliary variables Y with the property that, for boolean assignments
~a to X the following are satised:
The gadget is strict if, in addition,
We use the shorthand
w) to denote the gadget described above.
It is straightforward to verify that the introductory example yields a strict 7-
gadget reducing the constraint function to the family
2SAT.
6 L. TREVISAN, G. B. SORKIN, M. SUDAN, AND D. P. WILLIAMSON
Observe that an
w) can be converted into an  0 >  gadget
by \rescaling", i.e., multiplying every entry of the weight vector ~
w by
strictness is not preserved). This indicates that a \strong" gadget is one with a
small ; in the extreme, a 1-gadget would be the \optimal" gadget. This intuition
will be conrmed in the role played by gadgets in the construction of reductions.
Before describing this, we rst list the constraints and constraint families that are of
interest to us.
For convenience we now give a comprehensive list of all the constraints and constraint
families used in this paper.
Definition 2.6.
Parity check (PC) is the constraint family fPC
f0; 1g, PC i is dened as follows:
Henceforth we will simply use terms such as MAX PC to denote the optimization
problem MAX F where (referred to as MAX 3LIN in [9]) is the
source of all our inapproximability results.
For any k  1, Exactly-k-SAT (EkSAT) is the constraint family ff :
that is, the set of k-ary disjunctive
constraints.
For any k  1, kSAT is the constraint family
SAT is the constraint family
l1 ElSAT.
The problems MAX 3SAT, MAX 2SAT, and MAX SAT are by now classical optimization
problems. They were considered originally in [6]; subsequently their central
role in approximation was highlighted in [15]; and recently, novel approximation algorithms
were developed in [7, 8, 5]. The associated families are typically the targets of
gadget constructions in this paper. Shortly, we will describe a lemma which connects
the inapproximability of MAX F to the existence of gadgets reducing PC 0 and PC 1
to F . This method has so far yielded in several cases tight, and in other cases the
best known, inapproximability results for MAX F problems.
In addition to 3SAT's use as a target, its members are also used as sources; gadgets
reducing members of MAX 3SAT to MAX 2SAT help give an improved MAX 3SAT
approximation algorithm.
3-Conjunctive SAT (3ConjSAT) is the constraint family ff 000
where:
1. f 000 (a; b; c)
2. f 001 (a; b; c)
3. f 011 (a; b; c)
4. f 111 (a; b; c)
Members of 3ConjSAT are sources in gadgets reducing them to 2SAT. These gadgets
enable a better approximation algorithm for the MAX 3ConjSAT problem, which in
turn sheds light on the the class PCP c;s [log; 3].
is the constraint function given by CUT(a; a b.
CUT/0 is the family of constraints fCUT;Tg, where
CUT/1 is the family of constraints fCUT;Fg, where
GADGETS, APPROXIMATION, AND LINEAR PROGRAMMING 7
MAX CUT is again a classical optimization problem. It has attracted attention due
to the recent result of Goemans and Williamson [8] providing a .878-approximation
algorithm. An observation from Bellare et al. [2] shows that the approximability of
MAX CUT/0, MAX CUT/1, and MAX CUT are all identical; this is also formalized
in Proposition 4.1 below. Hence MAX CUT/0 becomes the target of gadget constructions
in this paper, allowing us to get inapproximability results for these three
problems.
is the constraint function given by DICUT(a;
MAX DICUT is another optimization problem to which the algorithmic results of
[8, 5] apply. Gadgets whose target is DICUT will enable us to get inapproximability
results for MAX DICUT.
2CSP is the constraint family consisting of all binary functions, i.e.
MAX 2CSP was considered in [5], which gives a .859-approximation algorithm; here
we provide inapproximability results.
Respect of monomial basis check (RMBC) is the constraint family
may be thought of as the test (c; d)[a] ?
as the test
as the test (:c; d)[a] ?
as the test
b, where the notation (v refers to the i 1'st coordinate
of the vector (v
Our original interest in RMBC came from the work of Bellare et al. [2] which derived
hardness results for MAX F using gadgets reducing every constraint function in PC
and RMBC to F . This work has been eectively superseded by Hastad's [9] which
only requires gadgets reducing members of PC to F . However we retain some of
the discussion regarding gadgets with RMBC functions as a source, since these constructions
were signicantly more challenging, and some of the techniques applied to
overcome the challenges may be applicable in other gadget constructions. A summary
of all the gadgets we found, with their performances and lower bounds, is given in

Table

1.
We now put forth a theorem, essentially from [2] (and obtainable as a generalization
of its Lemmas 4.7 and 4.15), that relates the existence of gadgets with F as
target, to the hardness of approximating MAX F . Since we will not be using this
theorem, except as a motivation for studying the family RMBC, we do not prove it
here.
Theorem 2.7. For any family F , if there exists an  1 -gadget reducing every
function in PC to F and an  2 -gadget reducing every function in RMBC to F , then
for any  > 0, MAX F is hard to approximate to within 1 :15
.
In this paper we will use the following, stronger, result by Hastad.
Theorem 2.8. [9] For any family F , if there exists an  0 -gadget reducing PC 0
to F and an  1 -gadget reducing PC 1 to F , then for any  > 0, MAX F is hard to
approximate to within 1 1
8 L. TREVISAN, G. B. SORKIN, M. SUDAN, AND D. P. WILLIAMSON
source previous  our  lower bound

Table
All gadgets described are provably optimal, and strict. The sole exception (y) is the best possible
strict gadget; there is a non-strict 3-gadget. All \previous" results quoted are interpretations of the
results in [2], except the gadget reducing 3SAT to 2SAT, which is due to [6], and the gadget reducing
PC to 3SAT, which is folklore.
Thus, using CUT=0, DICUT, 2CSP, EkSAT and kSAT as the target of gadget constructions
from PC 0 and PC 1 , we can show the hardness of MAX CUT, MAX DICUT,
MAX 2CSP, MAX EkSAT and MAX kSAT respectively. Furthermore, minimizing
the value of  in the gadgets gives better hardness results.
3. The Basic Procedure. The key aspect of making the gadget search spaces
nite is to limit the number of auxiliary variables, by showing that duplicates (in a
sense to be claried) can be eliminated by means of proper substitutions. In general,
this is possible if the target of the reduction is a \hereditary" family as dened below.
Definition 3.1. A constraint family F is hereditary if for any f 2 F of
arity k, and any two indices [k], the function f when restricted to X i  X j
and considered as a function of k 1 variables, is identical (up to the order of the
arguments) to some other function f 0 2 F [f0; 1g (where 0 and 1 denote the constant
functions).
Definition 3.2. A family F is complementation-closed if it is hereditary
and, for any f 2 F of arity k, and any index i 2 [k], the function f 0 given by
contained in F .
Definition 3.3 (Partial Gadget). For
and a constraint family F : an S-partial -gadget (or
\S-partial gadget with performance ") reducing f to F is a nite collection of constraints
Cm from F over primary variables and nitely many aux-
GADGETS, APPROXIMATION, AND LINEAR PROGRAMMING 9
iliary variables Y a collection of non-negative real weights w
with the property that, for boolean assignments ~a to X
the following are satised:
We use the shorthand
w) to denote the partial gadget.
The following proposition follows immediately from the denitions of a gadget
and a partial gadget.
Proposition 3.4. For a constraint function
. Then for every
family
1. An S 1 -partial -gadget reducing f to F is an -gadget reducing f to F .
2. An S 2 -partial -gadget reducing f to F is a strict -gadget reducing f to F .
Definition 3.5. For   1 and S  f0; 1g k ,
w) be an S-partial
-gadget reducing a constraint f : f0; 1g k ! f0; 1g to a constraint family F . We say
that the function b is a witness for the partial gadget, witnessing the
set S, if b(~a) satises equations (3.2) and (3.4). Specically:
The witness function can also be represented as an jSj
rows are the vectors (~a; b(~a)). Notice that the columns of the matrix correspond to the
variables of the gadget, with the rst k columns corresponding to primary variables,
and the last n corresponding to auxiliary variables. In what follows we shall often
prefer the matrix notation.
Definition 3.6. For a set S  f0; 1g k let MS be the matrix whose rows are
the vectors ~a 2 S, let k 0
S be the number of distinct columns in MS , and let k 00
S be
the number of columns in MS distinct up to complementation. Given a constraint f
of arity k and a hereditary constraint family F that is not complementation-closed,
an (S; f; F)-canonical witness matrix (for an S-partial gadget reducing f to F)
is the jSj
whose rst k columns correspond to the k
primary variables and whose remaining columns are all possible column vectors that
L. TREVISAN, G. B. SORKIN, M. SUDAN, AND D. P. WILLIAMSON
are distinct from one another and from the columns corresponding to the primary
variables. If F is complementation-closed, then a canonical witness matrix is the
whose rst k columns correspond to the k primary
variables and whose remaining columns are all possible column vectors that are distinct
up to complementation from one another and from the columns corresponding to the
primary variables.
The following lemma is the crux of this paper and establishes that the optimal
gadget reducing a constraint function f to a hereditary family F is nite. To motivate
the lemma, we rst present an example, due to Karlo and Zwick [11], showing that
this need not hold if the family F is not hereditary. Their counterexample has
g. Using k auxiliary variables, Y may construct a gadget
for the constraint X , using the constraints X  Y with each
constraint having the same weight. For an appropriate choice of this weight it may
be veried that this yields a (2 2=k)-gadget for even k; thus the performance tends
to 2 in the limit. On the other hand it can be shown that any gadget with k auxiliary
variables has performance at most 2 thus no nite gadget achieves the limit.
It is clear that for this example the lack of hereditariness is critical: any hereditary
family containing PC 1 would also contain f , providing a trivial 1-gadget.
To see why the hereditary property helps in general, consider an -gadget
reducing f to F , and let W be a witness matrix for . Suppose two columns of W ,
corresponding to auxiliary variables Y 1 and Y 2 of , are identical. Then we claim that
does not really need the variable Y 2 . In every constraint containing Y 2 , replace it
with Y 1 , to yield a new collection of weighted constraints. By the hereditary property
of F , all the resulting constraints are from F . And, the resulting instance satises
all the properties of an -gadget. (The universal properties follow trivially, while
the existential properties follow from the fact that in the witness matrix Y 1 and Y 2
have the same assignment.) Thus this collection of constraints forms a gadget with
fewer variables and performance at least as good. The niteness follows from the
fact a witness matrix with distinct columns has a bounded number of columns. The
following lemma formalizes this argument. In addition it also describes the canonical
witness matrix for an optimal gadget | something that will be of use later.
Lemma 3.7. For   1, set S  f0; 1g k , constraint
hereditary constraint family F, if there exists an S-partial -gadget reducing f to
F , with witness matrix W , then for any (S; f; F)-canonical witness matrix W 0 , and
some  0  , there exists an  0 -gadget 0 reducing f to F , with W 0 as a witness
matrix.
Proof. We rst consider the case where F is not complementation-closed. Let
w) be an S-partial -gadget reducing f to F and let W be a witness
matrix for . We create a gadget 0 with auxiliary variables Y 0
one associated with each column of the matrix W 0 other than the rst k.
With each variable Y i of we associate a variable Z such that the column corresponding
to Y i in W is the same as the column corresponding to Z in W 0 . Notice that
Z may be one of the primary variables or one of the auxiliary variables
By denition of a canonical witness, such a column and hence variable Z
does exist.
Now for every constraint C j on variables Y i 1
in with weight w j , we
introduce the constraint C j on variables Y 0
in 0 with weight w j where Y 0
is the variable associated with Y i l . Notice that in this process the variables involved
GADGETS, APPROXIMATION, AND LINEAR PROGRAMMING 11
with a constraint do not necessarily remain distinct. This is where the hereditary
property of F is used to ensure that a constraint C j 2 F , when applied to a tuple
of non-distinct variables, remains a constraint in F . In the process we may arrive
at some constraints which are either always satised or never satised. For the time
being, we assume that the constraints 0 and 1 are contained in F , so this occurrence
does not cause a problem. Later we show how this assumption is removed.
This completes the description of 0 . To verify that 0 is indeed an S-partial
-gadget, we notice that the universal constraints (conditions (3.1) and (3.3) in Definition
are trivially satised, since 0 is obtained from by renaming some variables
and possibly identifying some others. To see that the existential constraints
(conditions (3.2) and (3.4) in Denition 3.3) are satised, notice that the assignments
to the variables ~
Y that witness these conditions in are allowable assignments to
the corresponding variables in ~ Y 0 and in fact this is what dictated our association of
variables in ~
Y to the variables in ~
Y 0 . Thus 0 is indeed an S-partial -gadget reducing
f to F , and, by construction, has W 0 as a witness matrix.
Last, we remove the assumption that 0 must include constraints 0 and 1. Any
constraints 0 can be safely thrown out of the gadget without changing any of the pa-
rameters, since such constraints are never satised. On the other hand, constraints 1
do aect . If we throw away a 1 constraint of weight w j , this reduces the total weight
of satised clauses in every assignment by w j . Throwing away all such constraints
reduces  by the total weight of the 1 constraints, producing a gadget of (improved)
performance  0  .
Finally, we describe the modications required to handle the case where F is
complementation-closed (in which case the denition of a canonical witness changes).
Here, for each variable Y i and its associated column of W , either there is an equal
column in W 0 , in which case we replace Y i with the column's associated variable
or there is a complementary column in W 0 , in which case we replace Y i with
the negation of the column's associated variable, :Y 0
The rest of the construction
proceeds as above, and the proof of correctness is the same.
It is an immediate consequence of Lemma 3.7 that an optimum gadget reducing a
constraint function to a hereditary family does not need to use more than an explicitly
bounded number of auxiliary variable.
Corollary 3.8. Let f be a constraint function of arity k with s satisfying
assignments. Let F be a constraint family and   1 be such that there exists an
-gadget reducing f to F .
1. If F is hereditary then there exists an  0 -gadget with at most 2 s k 0 auxiliary
variables reducing f to F , where  0  , and k 0 is the number of distinct
variables among the satisfying assignments of f .
2. If F is complementation-closed then there exists an  0 -gadget with at most
auxiliary variables reducing f to F , for some  0  , where k 00 is
the number of distinct variables, up to complementation, among the satisfying
assignments of f .
Corollary 3.9. Let f be a constraint function of arity k. Let F be a constraint
family and   1 be such that there exists a strict -gadget reducing f to F .
1. If F is hereditary then there exists a strict  0 -gadget with at most 2 2 k
auxiliary variables reducing f to F , for some  0  .
2. If F is complementation-closed then there exists a strict  0 -gadget with at
most auxiliary variables reducing f to F , for some  0  .
L. TREVISAN, G. B. SORKIN, M. SUDAN, AND D. P. WILLIAMSON
We will now show how to cast the search for an optimum gadget as a linear programming
problem.
Definition 3.10. For a constraint function f of arity k, constraint family F ,
M) is a linear program dened as follows:
Cm be all the possible distinct constraints that arise from applying
a constraint function from F to a set of n variables. Thus for
every j, 1g. The LP variables are w
corresponds to the weight of the constraint C j . Additionally the LP has one
more variable .
Let S  f0; 1g k and b be such that (i.e., M is the
witness matrix corresponding to the witness function b for the set S). The
LP inequalities correspond to the denition of an S-partial gadget.
Finally the LP has the inequalities w j  0.
The objective of the LP is to minimize .
Proposition 3.11. For any constraint function f of arity k, constraint family
F , and s  witnessing the set S  f0; 1g k , if there exists
an S-partial gadget reducing f to F with witness matrix M , then LP(f; F ; M) nds
such a gadget with the minimum possible .
Proof. The LP-generated gadget consists of k primary variables corresponding
to the rst k columns of M ; n auxiliary variables Y corresponding
to the remaining n columns of M ; constraints C as dened in Denition 3.10;
and weights w returned by LP(f; F ; M ). By construction the LP solution
returns the minimum possible  for which an S-partial -gadget reducing f to F with
witness M exists.
Theorem 3.12 (Main). Let f be a constraint function of arity k with s satisfying
assignments. Let k 0 be the number of distinct variables of f and k 00 be the number
of distinct variables up to complementation. Let F be a hereditary constraint family
with functions of arity at most l. Then:
If there exists an -gadget reducing f to F , then there exists such a gadget with
at most v auxiliary variables, where
closed and
If there exists a strict -gadget reducing f to F then there exists such a
gadget with at most v auxiliary variables, where
complementation-closed and
Furthermore such a gadget with smallest performance can be found by solving a linear
program with at most jF j  (v variables and 2 v+k constraints.
GADGETS, APPROXIMATION, AND LINEAR PROGRAMMING 13
Remark: The sizes given above are upper bounds. In specic instances, the sizes
may be much smaller. In particular, if the constraints of F exhibit symmetries, or
are not all of the same arity, then the number of variables of the linear program will
be much smaller.
Proof. By Proposition 3.11 and Lemma 3.7, we have that LP(f; F ; WS ) yields
an optimal S-partial gadget if one exists. By Proposition 3.4 the setting
gadget, and the setting strict gadget.
Corollaries 3.8 and 3.9 give the required bound on the number of auxiliary variables;
and the size of the LP then follows from the denition.
To conclude this section, we mention some (obvious) facts that become relevant
when searching for large gadgets. First, if S 0  S, then the performance of an S 0 -
partial gadget reducing f to F is also a lower bound on the performance of an S-partial
gadget reducing f to F . The advantage here is that the search for an S 0 -partial gadget
may be much faster. Similarly, to get upper bounds on the performance of an S-partial
gadget, one may use other witness matrices for S (rather than the canonical one); in
particular ones with (many) fewer columns. This corresponds to making a choice of
auxiliary variables not to be used in such a gadget.
4. Improved Negative Results.
4.1. MAX CUT. We begin by showing an improved hardness result for the
MAX CUT problem. It is not di-cult to see that no gadget per Denition 2.5 can
reduce any member of PC to CUT: for any setting of the variables which satises
equation (2.2), the complementary setting has the opposite parity (so that it must be
subject to inequality (2.3)), but the values of all the CUT constraints are unchanged,
so that the gadget's value is still , violating (2.3). Following [2], we use instead the
fact that MAX CUT and MAX CUT/0 are equivalent with respect to approximation
as shown below.
Proposition 4.1. MAX CUT is equivalent to MAX CUT/0. Specically, given
an instance I of either problem, we can create an an instance I 0 of the other with the
same optimum and with the feature that an assignment satisfying constraints of total
weight W to the latter can be transformed into an assignment satisfying constraints
of the same total weight in I.
Proof. The reduction from MAX CUT to MAX CUT/0 is trivial, since the family
CUT/0 contains CUT; and thus the identity map provides the required reduction.
In the reverse direction, given an instance ( ~
w) of MAX CUT/0 with n
variables and m clauses, we create an instance ( ~
w) of MAX CUT with
variables and m clauses. The variables are simply the variables ~
X with one additional
variable called 0. The constraints of ~
C are transformed as follows. If the constraint
is a CUT constraint on variables X i and X j it is retained as is. If the constraint is
replaced with the constraint CUT(X Given a assignment ~a to the
vector ~
notice that its complement also satises the same number of constraints
in I 0 . We pick the one among the two that sets the variable 0 to 0, and then observe
that the induced assignment to ~
X satises the corresponding clauses of I.
Thus we can look for reductions to CUT/0. Notice that the CUT=0 constraint
family is hereditary, since identifying the two variables in a CUT constraint yields the
constant function 0. Thus by Theorem 3.12, if there is an -gadget reducing PC 0 to
CUT=0, then there is an -gadget with at most 13 auxiliary variables (16 variables
in all). Only are possible on 16 variables. Since we only
14 L. TREVISAN, G. B. SORKIN, M. SUDAN, AND D. P. WILLIAMSONx 1
Fig. 4.1. 8-gadget reducing PC 0 to CUT. Every edge has weight .5. The auxiliary variable
which is always 0 is labelled 0.
need to consider the cases when Y 0, we can construct a linear program as above
with constraints to nd the optimal -gadget reducing PC 0 to
CUT=0. A linear program of the same size can similarly be constructed to nd a
gadget reducing PC 1 to CUT=0.
Lemma 4.2. There exists an 8-gadget reducing PC 0 to CUT=0, and it is optimal
and strict.
We show the resulting gadget in Figure 4.1 as a graph. The primary variables are
labelled is a special variable. The unlabelled vertices are
auxiliary variables. Each constraint of non-zero weight is shown as an edge. An edge
between the vertex 0 and some vertex x corresponds to the constraint T (x). Any
other edge between x and y represents the constraint CUT(x; y). Note that some of
the 13 possible auxiliary variables do not appear in any positive weight constraint and
thus are omitted from the graph. All non-zero weight constraints have weight .5.
By the same methodology, we can prove the following.
Lemma 4.3. There exists a 9-gadget reducing PC 1 to CUT=0, and it is optimal
and strict.
The gadget is similar to the previous one, but the old vertex 0 is renamed Z, and
a new vertex labelled 0 is joined to Z by an edge of weight 1.
The two lemmas along with Proposition 4.1 above imply the following theorem.
Theorem 4.4. For every  > 0, MAX CUT is hard to approximate to within
Proof. Combining Theorem 2.8 with Lemmas 4.2 and 4.3 we nd that MAX CUT/0
is hard to approximate to within 16=17 . The theorem then follows from Proposition
4.1.
gadgets. Finding RMBC gadgets was more di-cult. We discuss this
point since it leads to ideas that can be applied in general when nding large gad-
gets. Indeed, it turned out that we couldn't exactly apply the technique above
to nd an optimal gadget reducing, say, RMBC 00 to CUT=0. (Recall that the
is the function (a 3 ; a 4
.) Since there are 8 satisfying
assignments to the 4 variables of the RMBC 00 constraint, by Theorem 3.12, we would
need to consider 2 auxiliary variables, leading to a linear program with
which is somewhat beyond the capacity of current computing
GADGETS, APPROXIMATION, AND LINEAR PROGRAMMING 15
machines. To overcome this di-culty, we observed that for the RMBC 00 function, the
value of a 4 is irrelevant when a and the value of a 3 is irrelevant when a
led us to try only restricted witness functions for which ~ b(0; a 2 ; a 3 ;
and ~ b(1; a (dropping from the witness matrix columns violating
the above conditions), even though it is not evident a priori that a gadget with
a witness function of this form exists. The number of distinct variable columns that
such a witness matrix can have is at most 16. Excluding auxiliary variables identical
to a 1 or a 2 , we considered gadgets with at most 14 auxiliary variables. We then created
a linear program with constraints.
The result of the linear program was that there exists an 8-gadget with constant 0
reducing RMBC 00 to CUT, and that it is strict. Since we used a restricted witness
function, the linear program does not prove that this gadget is optimal.
However, lower bounds can be established through construction of optimal S-
partial gadgets. If S is a subset of the set of satisfying assignments of RMBC 00 , then
its dening equalities and inequalities (see Denition 3.3) are a subset of those for a
gadget, and thus the performance of the partial gadget is a lower bound for that of a
true gadget.
In fact, we have always been lucky with the latter technique, in that some choice
of the set S has always yielded a lower bound and a matching gadget. In particular,
for reductions from RMBC to CUT, we have the following result.
Theorem 4.5. There is an 8-gadget reducing RMBC 00 to CUT=0, and it is
optimal and strict; there is an 8-gadget reducing RMBC 01 to CUT=0, and it is optimal
and strict; there is a 9-gadget reducing RMBC 10 to CUT=0, and it is optimal and
strict; and there is a 9-gadget reducing RMBC 11 to CUT=0, and it is optimal and
strict.
Proof. In each case, for some set S of satisfying assignments, an optimal S-
partial gadget also happens to be a true gadget, and strict. In the same notation as
in Denition 2.6, the appropriate sets S of 4-tuples (a; b; c; d) are: for RMBC 00 ,
4.2. MAX DICUT. As in the previous subsection, we observe that if there
exists an -gadget reducing an element of PC to DICUT, there exists an -gadget with
auxiliary variables. This leads to linear programs with 1615 variables (one for each
possible DICUT constraint, corresponding to a directed edge) and 2
linear constraints. The solution to the linear programs gives the following.
Lemma 4.6. There exist 6:5-gadgets reducing PC 0 and PC 1 to DICUT, and they
are optimal and strict.
The PC 0 gadget is shown in Figure 4.2. Again x 1 , x 2 and x 3 refer to the primary
variable and an edge from x to y represents the constraint :x^b. The PC 1 gadget is
similar, but has all edges reversed.
Theorem 4.7. For every  > 0, MAX DICUT is hard to approximate to within
gadgets. As with the reductions to CUT=0, reductions from the RMBC
family members to DICUT can be done by constructing optimal S-partial gadgets,
and again (with fortuitous choices of S) these turn out to be true gadgets, and strict.
Theorem 4.8. There is a 6-gadget reducing RMBC 00 to DICUT, and it is
optimal and strict; there is a 6.5-gadget reducing RMBC 01 to DICUT, and it is optimal
and strict; there is a 6.5-gadget reducing RMBC 10 to DICUT, and it is optimal and
L. TREVISAN, G. B. SORKIN, M. SUDAN, AND D. P. WILLIAMSON3
Fig. 4.2. 8-gadget reducing PC 0 to DICUT. Edges have weight 1 except when marked otherwise.
strict; and there is a 7-gadget reducing RMBC 11 to DICUT, and it is optimal and
strict.
Proof. Using, case by case, the same sets S as in the proof of Theorem 4.5, again
yields in each case an optimal S-partial gadget that also happens to be a true, strict
gadget.
4.3. MAX 2-CSP. For reducing an element of PC to the 2CSP family we need
consider only 4 auxiliary variables, for a total of 7 variables. There are two non-constant
functions on a single variable, and twelve non-constant functions on pairs of
variables, so that there are 2  7 functions to consider overall. We can
again set up a linear program with a variable per function and 2 7 linear
constraints. We obtain the following.
Lemma 4.9. There exist 5-gadgets reducing PC 0 and PC 1 to 2CSP, and they are
optimal and strict.
The gadget reducing PC 0 to 2CSP is the following:
The gadget reducing PC 1 to 2CSP can be obtained from this one by complementing
all the occurrences of X 1 .
Theorem 4.10. For every  > 0, MAX 2CSP is hard to approximate to within
MAX 2CSP can be approximated within :859 [5]. The above theorem has implications
for probabilistically checkable proofs. Reversing the well-known reduction
from constraint satisfaction problems to probabilistically checkable proofs (cf. [1]) 3 ,
Theorem 4.10 yields the following theorem.
Theorem 4.11. For any  > 0, constants c and s exist such that NP
c;s [log; 2] and c=s > 10=9 .
The previously known gap between the completeness and soundness achievable reading
two bits was 74=73 [2]. It would be 22=21  using Hastad's result [9] in combination
3 The reverse connection is by now a folklore result and may be proved along the lines of [2,
Proposition 10.3, Part (3)].
GADGETS, APPROXIMATION, AND LINEAR PROGRAMMING 17
with the argument of [2]. Actually the reduction from constraint satisfaction problems
to probabilistically checkable proofs is reversible, and this will be important in Section
7.
RMBC gadgets. Theorem 4.12. For each element of RMBC, there is a 5-gadget
reducing it to 2CSP, and it is optimal and strict.
Proof. Using the same selected assignments as in Theorems 4.5 and 4.8 again
yields lower bounds and matching strict gadgets.
5. Interlude: Methodology. Despite their seeming variety, all the gadgets in
this paper were computed using a single program (in the language APL2) to generate
an LP, and call upon OSL (the IBM Optimization Subroutine Library) to solve it.
This \gadget-generating" program takes several parameters.
The source function f is specied explicitly, by a small program that computes
f .
The target family F is described by a single function, implemented as a small
program, applied to all possible clauses of specied lengths and symmetries. The
symmetries are chosen from among: whether clauses are unordered or ordered; whether
their variables may be complemented; and whether they may include the constants 0
or 1. For example, a reduction to MAX CUT=0 would take as F the function x 1 x 2 ,
applied over unordered binomial clauses, in which complementation is not allowed
but the constant 0 is allowed. This means of describing F is relatively intuitive and
has never restricted us, even though it is not completely general. Finally, we specify
an arbitrary set S of selected assignments, which allows us to search for S-partial
gadgets (recall Denition 3.3). From equations (3.2) and (3.4), each selected assignment
~a generates a constraint that
Selecting
all satisfying assignments of f reproduces the set of constraints (2.2) for an -gadget,
while selecting all assignments reproduces the set of constraints (2.2) and (2.4) for a
strict -gadget.
Selected assignments are specied explicitly; by default, to produce an ordinary
gadget, they are the satisfying assignments of f . The canonical witness for the selected
set of assignments is generated by our program as governed by Denition 3.6. Notice
that the denition of the witness depends on whether F is complementation-closed
or not, and this is determined by the explicitly specied symmetries.
To facilitate the generation of restricted witness matrices, we have also made
use of a \don't-care" state (in lieu of 0 or 1) to reduce the number of selected assign-
ments. For example in reductions from RMBC 00 we have used selected assignments
of (00  1). The various LP constraints must be satised
for both values of any don't-care, while the witness function must not depend on
the don't-care values. So in this example, use of a don't-care reduces the number
of selected assignments from 8 to 4, reduces the number of auxiliary variables from
about 2 8 to 2 4 (ignoring duplications of the 4 primary variables, or any symmetries),
and reduces the number of constraints in the LP from 2 2 8
(a
more reasonable 65,536). Use of don't-cares provides a technique complementary to
selecting a subset of all satisfying assignments, in that if the LP is feasible it provides
an upper bound and a gadget, but the gadget may not be optimal.
In practice, selecting a subset of satisfying assignments has been by far the more
useful of the two techniques; so far we have always been able to choose a subset which
produces a lower bound and a gadget to match.
L. TREVISAN, G. B. SORKIN, M. SUDAN, AND D. P. WILLIAMSON
After constructing and solving an LP, the gadget-generating program uses brute
force to make an independent verication of the gadget's validity, performance, and
strictness.
The hardest computations were those for gadgets reducing from RMBC; on an
IBM Risc System/6000 model 43P-240 workstation, running at 233MHz, these took
up to half an hour and used 500MB or so of memory. However, the strength of [9]
makes PC virtually the sole source function of contemporary interest, and all the
reductions from PC are easy; they use very little memory, and run in seconds on an
ordinary 233MHz Pentium processor.
6. Improved Positive Results. In this section we show that we can use gadgets
to improve approximation algorithms. In particular, we look at MAX 3SAT, and
a variation, MAX 3ConjSAT, in which each clause is a conjunction (rather than a
disjunction) of three literals. An improved approximation algorithm for the latter
problem leads to improved results for probabilistically checkable proofs in which the
verier examines only 3 bits. Both of the improved approximation algorithms rely on
strict gadgets reducing the problem to MAX 2SAT. We begin with some notation.
Definition 6.1. A )-approximation algorithm for MAX 2SAT is an algorithm
which receives as input an instance with unary clauses of total weight m 1 and
binary clauses of total weight m 2 , and two reals produces
reals s 1  u 1 and s 2  u 2 and an assignment satisfying clauses of total weight at
least . If there exists an optimum solution that satises unary clauses of
weight no more than u 1 and binary clauses of weight no more than u 2 , then there is a
guarantee that no assignment satises clauses of total weight more than s 1 +s 2 . That
is, supplied with a pair of \upper bounds" )-approximation algorithm
produces a single upper bound of s 1 +s 2 , along with an assignment respecting a lower
bound of  1
Lemma 6.2. [5] There exists a polynomial-time (:976; :931)-approximation algorithm
for MAX 2SAT.
6.1. MAX 3SAT. In this section we show how to derive an improved approximation
algorithm for MAX 3SAT. By restricting techniques in [8] from MAX SAT to
MAX 3SAT and using a :931-approximation algorithm for MAX 2SAT due to Feige
and Goemans [5], one can obtain a :7704-approximation algorithm for MAX 3SAT.
The basic idea of [8] is to reduce each clause of length 3 to the three possible subclauses
of length 2, give each new length-2 clause one-third the original weight, and
then apply an approximation algorithm for MAX 2SAT. This approximation algorithm
is then \balanced" with another approximation algorithm for MAX 3SAT to
obtain the result. Here we show that by using a strict gadget to reduce 3SAT to
MAX 2SAT, a good )-approximation algorithm for MAX 2SAT leads to a :801-
approximation algorithm for MAX 3SAT.
Lemma 6.3. If for every f 2 E3SAT there exists a strict -gadget reducing f
to 2SAT, there exists a )-approximation algorithm for MAX 2SAT, and
there exists a -approximation algorithm for MAX 3SAT with
Proof. Let  be an instance of MAX 3SAT with length-1 clauses of total weight
clauses of total weight m 2 , and length-3 clauses of total weight m 3 .
GADGETS, APPROXIMATION, AND LINEAR PROGRAMMING 19
We use the two algorithms listed below, getting the corresponding upper and lower
bounds on number of satisable clauses:
Random: We set each variable to 1 with probability 1=2. This gives a solution
of weight at least m 1
Semidenite programming: We use the strict -gadget to reduce every length-
3 clause to length-2 clauses. This gives an instance of MAX 2SAT. We apply
the )-approximation algorithm with parameters
to nd an approximate solution to this problem. The approximation
algorithm gives an upper bound s 1 on the weight of any solution to
the MAX 2SAT instance and an assignment of weight  1
translated back to the MAX 3SAT instance, the assignment has weight at
least
and the maximum weight satisable in the MAX 3SAT instance is at most
The performance guarantee of the algorithm which takes the better of the two
solutions is at least
We now dene a sequence of simplications which will help prove the bound.
To nish the proof of the lemma, we claim that
To see this, notice that the rst inequality follows from the substitution of variables
. The second follows from the fact that setting m 1 to t 1
only reduces the numerator. The third inequality follows
from setting . The fourth is obtained by substituting a convex combination
of the arguments instead of max and then simplifying. The convex combination takes
a  1 fraction of the rst argument,  2 of the second and  3 of the third, where
L. TREVISAN, G. B. SORKIN, M. SUDAN, AND D. P. WILLIAMSON
3:
Observe that  1 and that the condition on  guarantees that  2  0.
Remark 6.4. The analysis given in the proof of the above lemma is tight. In
particular for an instance with m clauses such that
is easy to see that
The following lemma gives the strict gadget reducing functions in E3SAT to
2SAT. Notice that nding strict gadgets is almost as forbidding as nding gadgets
for RMBC, since there are 8 existential constraints in the specication of a gadget.
This time we relied instead on luck. We looked for an S-partial gadget for the set
found an S-partial 3:5-gadget that turned out to be a
gadget! Our choice of S was made judiciously, but we could have aorded to run
through all 8 sets S of size 4 in the hope that one would work.
Lemma 6.5. For every function f 2 E3SAT, there exists a strict (and optimal)
3:5-gadget reducing f to 2SAT.
Proof. Since 2SAT is complementation-closed, it is su-cient to present a 3:5-
gadget reducing (X 1 _X 2 _X 3 ) to 2SAT. The gadget is
every clause except the last has weight
1=2, and the last clause has weight 1.
Combining Lemmas 6.2, 6.3 and 6.5 we get a :801-approximation algorithm.
Theorem 6.6. MAX 3SAT has a polynomial-time :801-approximation algorithm

6.2. MAX 3-CONJ SAT. We now turn to the MAX 3ConjSAT problem. The
analysis is similar to that of Lemma 6.3.
Lemma 6.7. If for every f 2 3ConjSAT there exists a strict
reducing f to 2SAT composed of  1 length-1 clauses and  2 length-2 clauses, and
there exists a )-approximation algorithm for MAX 2SAT, then there exists a
-approximation algorithm for MAX 3ConjSAT with
=8
Proof. Let  be an instance of MAX 3ConjSAT with constraints of total weight
m. As in the MAX 3SAT case, we use two algorithms and take the better of the two
solutions:
Random: We set every variable to 1 with probability half. The total weight
of satised constraints is at least m=8.
GADGETS, APPROXIMATION, AND LINEAR PROGRAMMING 21
Semidenite programming: We use the strict -gadget to reduce any constraint
to 2SAT clauses. This gives an instance of MAX 2SAT and we use the
)-approximation algorithm with parameters
The algorithm returns an upper bound s 1 on the total weight of satisable
constraints in the MAX 2SAT instance, and an assignment of measure
at least  1 translated back to the MAX 3ConjSAT instance,
the measure of the assignment is at least  1
thermore, s 1   1 m, s 2   2 m, and the total weight of satisable constraints
in the MAX 3ConjSAT instance is at most s
Thus we get that the performance ratio of the algorithm which takes the better
of the two solutions above is at least
We now dene a sequence of simplications which will help prove the bound.
tmt
In order to prove the lemma, we claim that
To see this, observe that the rst inequality follows from the substitution of variables
1)m. The second follows from setting
The third inequality follows from the fact that setting t 2 to (1  1 )m only reduces
the numerator. The fourth is obtained by substituting a convex combination of the
arguments instead of max and then simplifying.
The following gadget was found by looking for an S-partial gadget for
011g.
Lemma 6.8. For any f 2 3ConjSAT there exists a strict (and optimal) 4-gadget
reducing f to 2SAT. The gadget is composed of one length-1 clause and three length-2
clauses.
Proof. Recall that 2SAT is complementation-closed, and thus it is su-cient to
exhibit a gadget reducing f(a 1 ; a 2 ; a 3 to 2SAT. Such gadget is Y ,
clauses have weight 1. The variables
are primary variables and Y is an auxiliary variable.
22 L. TREVISAN, G. B. SORKIN, M. SUDAN, AND D. P. WILLIAMSON
Theorem 6.9. MAX 3ConjSAT has a polynomial-time .367-approximation algorithm

It is shown by Trevisan [16, Theorem 18] that the above theorem has consequences
for PCP c;s [log; 3]. This is because the computation of the verier in such a proof
system can be described by a decision tree of depth 3, for every choice of random
string. Further, there is a 1-gadget reducing every function which can be computed
by a decision tree of depth k to kConjSAT.
Corollary 6.10. PCP c;s [log; 3]  P provided that c=s > 2:7214. The previous
best trade-o between completeness and soundness for polynomial-time PCP classes
was c=s > 4 [16].
7. Lower Bounds for Gadget Constructions. In this section we shall show
that some of the gadget constructions mentioned in this paper and in [2] are optimal,
and we shall prove lower bounds for some other gadget constructions.
The following result is useful to prove lower bounds for the RMBC family.
Lemma 7.1. If there exists an -gadget reducing an element of RMBC to a
complementation-closed constraint family F , then there exists an -gadget reducing
all elements of PC to F .
Proof. If a family F is complementation-closed, then an -gadget reducing an
element of PC (respectively RMBC) to F can be modied (using complementations)
to yield -gadgets reducing all elements of PC (respectively RMBC) to F . For this
reason, we will restrict our analysis to PC 0 and RMBC 00 gadgets. Note that, for any
be an  gadget over primary variables x auxiliary variables y
reducing RMBC to 2SAT. Let 0 be the gadget obtained from by imposing x 4  x
it is immediate to verify that 0 is an -gadget reducing PC 0 to F .
7.1. Reducing PC and RMBC to 2SAT. Theorem 7.2. If is an -gadget
reducing an element of PC to 2SAT, then   11.
Proof. It su-ces to consider PC 0 . We prove that the optimum of (LP1) is at
least 11. To this end, consider the dual program of (LP1). We have a variable y ~a; ~ b
for any ~a 2 f0; 1g 3 and any ~ b 2 f0; 1g 4 , plus additional variables ^
y ~a; ~ b opt (~a)
for any
opt is the \optimal" witness function dened in Section 3. The
formulation is
maximize
subject to P
y ~a; ~ b opt (~a)
(DUAL1)
There exists a feasible solution for (DUAL1) whose cost is 11.
Corollary 7.3. If is an -gadget reducing an element of RMBC to 2SAT,
then   11.
7.2. Reducing PC and RMBC to SAT. Theorem 7.4. If is an -gadget
reducing an element of PC to SAT, then   4.
GADGETS, APPROXIMATION, AND LINEAR PROGRAMMING 23
Proof. As in the proof of Theorem 7.2 we give a feasible solution to the dual
to obtain the lower bound. The linear program that nds the best gadget reducing
PC 0 to SAT is similar to (LP1), the only dierence being that a larger number N of
clauses are considered, namely,
. The dual program is then
maximize
subject to P
y ~a; ~ b opt (~a)
(DUAL2)
Consider now the following assignment of values to the variables of (DUAL2) (the
unspecied values have to be set to zero):
1where d is the Hamming distance between binary sequences. It is possible to show
that this is a feasible solution for (DUAL2) and it is immediate to verify that its cost
is 4.
Corollary 7.5. If is an -gadget reducing an element RMBC to SAT, then
7.3. Reducing kSAT to lSAT. Let k and l be any integers k > l  3. The
standard reduction from EkSAT to lSAT can be seen as a d(k 2)=(l 2)e-gadget.
In this section we shall show that this is asymptotically the best possible. Note that
since lSAT is complementation-closed we can restrict ourselves to considering just one
constraint function of EkSAT, say f(a
Theorem 7.6. For any k > l > 2, if is an -gadget reducing f to lSAT then
k=l.
Proof. We can write a linear program whose optimum gives the smallest  such
that an -gadget exists reducing f to lSAT. Let b be the witness function used to
formulate this linear program. We can assume that b is
-ary and we let
Also let N be the total number of constraints from lSAT that can be dened over
k +K variables. Assume some enumeration C of such constraints. The dual
LP is
maximize
subject to P
y ~a; ~ b kSAT lSAT (~a)
y ~a; ~ b kSAT lSAT (~a)
y ~a; ~ b kSAT lSAT (~a)
The witness function ~ b kSAT lSAT is an \optimal" witness function for gadgets reducing
kSAT to lSAT.
L. TREVISAN, G. B. SORKIN, M. SUDAN, AND D. P. WILLIAMSON
Let A k  f0; 1g k be the set of binary k-ary strings with exactly one non-zero
component (note that jA k be the k-ary string all
whose components are equal to 0 (respectively, 1). The following is a feasible solution
for (DUAL3) whose cost is k=l. We only specify non-zero values.
y ~a; ~ b kSAT lSAT (~a)
In view of the above lower bound, a gadget cannot provide an approximation-
preserving reduction from MAX SAT to MAX kSAT. More generally, there cannot be
an approximation-preserving gadget reduction from MAX SAT to, say, MAX (log n)SAT.
In partial contrast with this lower bound, Khanna et al. [13] have given an approximation-
preserving reduction from MAX SAT to MAX 3SAT and Crescenzi and Trevisan [4]
have provided a tight reduction between MAX SAT and MAX (log n)SAT, showing
that the two problems have the same approximation threshold.

Acknowledgments

. We thank Pierluigi Crescenzi and Oded Goldreich for several
helpful suggestions and remarks. We are grateful to John Forrest and David
Jensen for their assistance in e-ciently solving large linear programs. We thank
Howard Karlo and Uri Zwick for pointing out the error in the earlier version of
this paper, and the counterexample to our earlier claim. We thank the anonymous
referees for their numerous comments and suggestions leading to the restructuring of
Section 3.



--R

Proof veri
Free bits
To weight or not to weight: Where is the question?

Approximating the value of two prover proof systems
Some simpli
New 3/4-approximation algorithms for the maximum satis ability problem
Improved approximation algorithms for maximum cut and satis



Reducibility among combinatorial problems.
On syntactic versus computational views of approximability.
Approximation algorithms for the maximum satis

Parallel approximation algorithms using positive linear programming.

On the approximation of maximum satis
Approximation algorithms for constraint satisfaction problems involving at most three variables per constraint.
--TR

--CTR
Eran Halperin , Dror Livnat , Uri Zwick, MAX CUT in cubic graphs, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.506-513, January 06-08, 2002, San Francisco, California
Eran Halperin , Dror Livnat , Uri Zwick, MAX CUT in cubic graphs, Journal of Algorithms, v.53 n.2, p.169-185, November 2004
Gunnar Andersson , Lars Engebretsen, Property testers for dense constraint satisfaction programs on finite domains, Random Structures & Algorithms, v.21 n.1, p.14-32, August 2002
Takao Asano , David P. Williamson, Improved approximation algorithms for MAX SAT, Journal of Algorithms, v.42 n.1, p.173-202, January 2002
Manthey, Non-approximability of weighted multiple sequence alignment, Theoretical Computer Science, v.296 n.1, p.179-192, 4 March
Don Coppersmith , David Gamarnik , Mohammad Hajiaghayi , Gregory B. Sorkin, Random MAX SAT, random MAX CUT, and their phase transitions, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
Lane A. Hemaspaandra, SIGACT news complexity theory column 34, ACM SIGACT News, v.32 n.4, December 2001
Philippe Chapdelaine , Nadia Creignou, The Complexity of Boolean Constraint Satisfaction Local Search Problems, Annals of Mathematics and Artificial Intelligence, v.43 n.1-4, p.51-63, January 2005
Alexander D. Scott , Gregory B. Sorkin, Solving Sparse Random Instances of Max Cut and Max 2-CSP in Linear Expected Time, Combinatorics, Probability and Computing, v.15 n.1-2, p.281-315, January 2006
Johan Hstad, Some optimal inapproximability results, Journal of the ACM (JACM), v.48 n.4, p.798-859, July 2001
Amin Coja-Oghlan , Cristopher Moore , Vishal Sanwalani, MAX k-CUT and approximating the chromatic number of random graphs, Random Structures & Algorithms, v.28 n.3, p.289-322, May 2006
reductions;intractability;combinatorial optimization;approximation algorithms;NP-completeness;probabilistic proof systems