Authors Ishay Haviv, Oded Regev, Amnon Ta-Shma,
License CC-BY-ND-2.0
T HEORY OF C OMPUTING, Volume 3 (2007), pp. 45–60
http://theoryofcomputing.org
On the Hardness of Satisfiability with
Bounded Occurrences in the
Polynomial-Time Hierarchy
Ishay Haviv Oded Regev∗ Amnon Ta-Shma†
Received: July 28, 2006; published: March 28, 2007.
Abstract: In 1991, Papadimitriou and Yannakakis gave a reduction implying the NP-
hardness of approximating the problem 3-SAT with bounded occurrences. Their reduction
is based on expander graphs. We present an analogue of this result for the second level of
the polynomial-time hierarchy based on superconcentrator graphs. This resolves an open
question of Ko and Lin (1995) and should be useful in deriving inapproximability results
in the polynomial-time hierarchy.
More precisely, we show that given an instance of ∀∃-3-SAT in which every variable
occurs at most B times (for some absolute constant B), it is Π2 -hard to distinguish between
the following two cases: YES instances, in which for any assignment to the universal vari-
ables there exists an assignment to the existential variables that satisfies all the clauses, and
NO instances in which there exists an assignment to the universal variables such that any
∗ Supported by an Alon Fellowship, by the Binational Science Foundation, by the Israel Science Foundation, and by the EU
Integrated Project QAP.
† Supported by the Binational Science Foundation, by the Israel Science Foundation, and by the EU Integrated Project QAP.
ACM Classification: F.1.3
AMS Classification: 03D15, 68Q17
Key words and phrases: satisfiability, polynomial-time hierarchy, expander graphs, superconcentrator
graphs
Authors retain copyright to their work and grant Theory of Computing unlimited rights
to publish the work electronically and in hard copy. Use of the work is permitted as
long as the author(s) and the journal are properly acknowledged. For the detailed
copyright statement, see http://theoryofcomputing.org/copyright.html.
c 2007 Ishay Haviv, Oded Regev, and Amnon Ta-Shma DOI: 10.4086/toc.2007.v003a003
I. H AVIV, O. R EGEV, AND A. TA -S HMA
assignment to the existential variables satisfies at most a 1 − ε fraction of the clauses. We
also generalize this result to any level of the polynomial-time hierarchy.
1 Introduction
In the problem ∀∃-3-SAT, given a 3-CNF formula we have to decide whether for any assignment to a
set of universal variables X there exists an assignment to a set of existential variables Y , such that the
formula is satisfied. Here, by a 3-CNF formula we mean a conjunction of clauses where each clause
is a disjunction of at most 3 literals. This problem is a standard Π2 -complete problem. We denote the
corresponding gap problem by ∀∃-3-SAT[1 − ε1 , 1 − ε2 ] where 0 ≤ ε2 < ε1 ≤ 1. This is the problem
of deciding whether for any assignment to the universal variables there exists an assignment to the
existential variables such that at least a 1 − ε2 fraction of the clauses are satisfied, or there exists an
assignment to the universal variables such that any assignment to the existential variables satisfies at
most a 1 − ε1 fraction of the clauses. The one-sided error gap problem ∀∃-3-SAT[1 − ε, 1] is Π2 -hard
for some ε > 0, as was shown in [6]. This problem has the perfect completeness property, i. e., in YES
instances it is possible to satisfy all the clauses.
In this paper we consider a restriction of ∀∃-3-SAT, known as ∀∃-3-SAT-B. Here, each variable
appears at most B times where B is some constant. In [7], Ko and Lin showed that ∀∃-3-SAT-B[1 −
ε1 , 1 − ε2 ] is Π2 -hard for some constants B and 0 < ε2 < ε1 < 1. Our main result is that the problem is
still Π2 -hard for some ε1 > 0 with ε2 = 0, i. e., with perfect completeness. This solves an open question
given in [7].
Theorem 1.1. The problem ∀∃-3-SAT-B[1 − ε, 1] is Π2 -hard for some constants B and ε > 0. Moreover,
this is true even when the number of literals in each clause is exactly 3.
We note that the problem remains Π2 -hard even if the number of occurrences of universal variables
is bounded by 2 and the number of occurrences of existential variables is bounded by 3. As we will
explain later, these are the least possible constants for which the problem is still Π2 -hard unless the
polynomial-time hierarchy collapses. We believe that Theorem 1.1 is useful for deriving Π2 -hardness
results, as well as Π2 inapproximability results. In fact, Theorem 1.1 was crucial in a recent proof that
the covering radius problem on lattices with high norms is Π2 -hard [5]. Moreover, using Theorem 1.1,
one can simplify the proof that the covering radius on codes is Π2 -hard to approximate [4].
At a very high level, the proof is based on the following ideas. First, one can reduce the number
of occurrences of existential variables by an expander construction in much the same way as was done
by Papadimitriou and Yannakakis [10]. The main difficulty in the proof is in reducing the number of
occurrences of universal variables: If we duplicate universal variables (as is usually done in order to
reduce the number of occurrences), we have to deal with inconsistent assignments to the new universal
variables (this problem shows up in the completeness proof). The approach taken by Ko and Lin [7]
is to duplicate universal variables and to add existential variables on top of the universal variables.
Their construction, in a way, enables the existential variables to override inconsistent assignments to the
universal variables. Unfortunately, it seems that this technique cannot produce instances with perfect
completeness. In our approach we also duplicate the universal variables, but instead of using them
T HEORY OF C OMPUTING, Volume 3 (2007), pp. 45–60 46
O N THE H ARDNESS OF S ATISFIABILITY WITH B OUNDED O CCURRENCES
directly in the original clauses, we use a superconcentrator-based gadget, whose purpose is intuitively
to detect the majority among the duplicates of a universal variable. Crucially, this gadget requires only
a constant number of occurrences of each universal variable.
The rest of the paper is organized as follows. Section 2 provides some background about satisfiability
problems in the second level of the polynomial-time hierarchy and about some explicit expanders and
superconcentrators. In Section 3 we prove Theorem 1.1. Section 4 discusses the least possible value of
B for which the problem remains Π2 -hard. In Section 5 we generalize our main theorem to any level of
the polynomial-time hierarchy.
2 Preliminaries
2.1 Π2 satisfiability problem
A D-CNF formula over a set of variables is a conjunction of clauses where each clause is a disjunction
of at most D literals. Each literal is either a variable or its negation. A clause is satisfied by a Boolean
assignment to the variables if it contains at least one literal that evaluates to True.
For any reals 0 ≤ α < β ≤ 1 and positive integer D > 0, we define:
Definition 2.1 (∀∃-D-SAT[α, β ]). An instance of ∀∃-D-SAT[α, β ] is a D-CNF Boolean formula Ψ(X,Y )
over two sets of variables. We refer to variables in X as universal variables and to those in Y as existential
variables. In YES instances, for every assignment to X there exists an assignment to Y such that at least
a β fraction of the clauses are satisfied. In NO instances, there exists an assignment to X such that for
every assignment to Y at most an α fraction of the clauses are satisfied.
The problem ∀∃-D-SAT[α, β ] is the basic approximation problem in the second level of the
polynomial-time hierarchy (see [11, 12] for a recent survey on the topic of completeness and hard-
ness of approximation in the polynomial-time hierarchy). We also define some additional variants of
the above problem. For any B ≥ 1 the problem ∀∃-D-SAT-B[α, β ] is defined similarly except that each
variable occurs at most B times in Ψ. In the instances of the problem ∀∃-D-SAT-B∀ [α, β ], the bound B
on the number of occurrences applies only to the universal variables (as opposed to all variables).
In [7] it was shown that ∀∃-3-SAT-B[1 − ε1 , 1 − ε2 ] is Π2 -hard for some B and some 0 < ε2 < ε1 < 1.
As already mentioned, in Section 3 we show that it is Π2 -hard even for some B, ε1 > 0 and ε2 = 0.
2.2 Expanders and superconcentrators
In this subsection, we gather some standard results on explicit constructions of expanders and supercon-
centrators (where by explicit we mean constructible in polynomial time). The first shows the existence
of certain regular expanders.
Lemma 2.2 ([8, 9]). There exists a universal constant C1 such that for any integer n, there is an explicit
14-regular graph G = (V, E) with n ≤ |V | ≤ C1 n vertices, such that any nonempty set S ⊂ V satisfies
|E(S, S)| > min(|S|, |S|).
For the second, we need to define the notion of a superconcentrator.
T HEORY OF C OMPUTING, Volume 3 (2007), pp. 45–60 47
I. H AVIV, O. R EGEV, AND A. TA -S HMA
Definition 2.3 (n-superconcentrator). A directed acyclic graph G = (U ∪V ∪W, E) where U denotes
a set of n inputs (i. e., vertices with indegree 0) and V denotes a set of n outputs (i. e., vertices with
outdegree 0) is an n-superconcentrator if for any subset S of U and any subset T of V satisfying |S| = |T |,
there are |S| vertex-disjoint directed paths in G from S to T .
The explicit construction of sparse superconcentrators has been extensively studied. Gabber and
Galil [3] were the first to give an explicit expander-based construction of n-superconcentrator with O(n)
edges. Alon and Capalbo [1] presented the most economical known explicit n-superconcentrators, in
which the number of edges is 44n + O(1). Their construction is based on a modification of the well-
known construction of Ramanujan graphs by Lubotzky, Phillips and Sarnak [8] and by Margulis [9].
The following theorem of [1] summarizes some of the properties of their graphs.
Theorem 2.4 ([1]). There exists an absolute constant k > 0 for which the following holds. For any n
of the form k · 2l (l ≥ 0) there exists an explicit n-superconcentrator H = (U ∪ V ∪ W, E) with |E| =
44n + O(1) and all of whose vertices have indegree and outdegree at most 11.
In our reduction, we use a slight modification of the superconcentrator in Theorem 2.4. This graph
is described in the following claim (see Figure 1 for an illustration of the construction).
U
U ′′
W′
V
Figure 1: The graph G(6) . All edges are directed downwards. The marked subgraph is a 6-superconcen-
trator (but not necessarily the one from [1]).
Claim 2.5. There exist absolute constants c and d for which the following holds. For any natural n ≥ 1
there exists an explicit directed acyclic graph G(n) = (U ∪ V ∪ W, E) with a set U of 2n inputs (i. e.,
vertices with indegree 0) with outdegree 1 and a set V of n outputs (i. e., vertices with outdegree 0), such
that for any subset S of U of size |S| = n there are n vertex-disjoint directed paths from S to V . Moreover,
|E| ≤ cn and all indegrees and outdegrees in G(n) are bounded by d.
T HEORY OF C OMPUTING, Volume 3 (2007), pp. 45–60 48
O N THE H ARDNESS OF S ATISFIABILITY WITH B OUNDED O CCURRENCES
Proof. Fix some n ≥ 1. By Theorem 2.4 there exists an explicit n0 -superconcentrator H 0 = (U 0 ∪ V 0 ∪
W 0 , E 0 ) for some n + k ≤ n0 < 2(n + k) where k is the constant from Theorem 2.4, such that |E 0 | =
44n0 + O(1) and all its indegrees and outdegrees are bounded by 11. Denote by U 00 = {u001 , . . . , u00n } and
by V = {v1 , . . . , vn } arbitrary subsets of U 0 and V 0 of size exactly n.
In order to construct the graph G(n) we add to the graph H 0 the 2n vertices U = {u1 , . . . , u2n } and 2n
edges. The input set of the graph G(n) is U, and the output set of G(n) is V . For each i ∈ {1, . . . , n} we
add the directed edges (ui , u00i ) and (ui+n , vi ). In other words, we add to the graph two matchings of size
n: the first between the vertex sets {u1 , . . . , un } and U 00 , and the second between {un+1 , . . . , u2n } and V .
It is easy to see that our graph satisfies the required properties for large enough absolute constants c
and d. Let S ⊆ U be of size n, and define S1 = S ∩ {ui : 1 ≤ i ≤ n} and S2 = S ∩ {ui : n + 1 ≤ i ≤ 2n}.
We show that there exist n vertex-disjoint paths from S to V . According to our construction, the vertices
of S2 have paths of length 1 to their neighbors in V . So it suffices to show that the vertices of S1 have
vertex-disjoint paths to the n − |S2 | = |S1 | remaining vertices of V . According to the property of H 0 ,
there exist vertex-disjoint paths in G(n) between the neighbors of S1 in U 00 and the n − |S2 | vertices of V .
Combining these paths together with the matching edges between S1 and U 00 completes the proof.
3 Hardness of approximation for ∀∃-3-SAT-B
In this section we prove Theorem 1.1. The proof is by reduction from the problem ∀∃-3-SAT[1 − ε, 1],
which was shown to be Π2 -hard for some ε > 0 in [6]. The reduction is performed in three steps. The
first step is the main one, and it is here that we present our new superconcentrator-based construction.
The remaining two steps are standard (see for example [14] and [2]) and we include them mainly for
completeness. We remark that these two steps are also used in [7].
Step 1: Here we reduce the number of occurrences of each universal variable to at most some constant
B. As a side effect, the size of the clauses grows from being at most 3 to being at most D, where D
is some constant. More precisely, we establish that there exist absolute constants B, D and ε > 0
such that the problem ∀∃-D-SAT-B∀ [1 − ε, 1] is Π2 -hard.
Step 2: Here we reduce the number of occurrences of the existential variables to some constant B.
Notice that we must make sure that this does not affect the number of occurrences of the universal
variables. More precisely, we show that there exist absolute constants B, D and ε > 0 such that
the problem ∀∃-D-SAT-B[1 − ε, 1] is Π2 -hard.
Step 3: Finally, we modify the formula such that the size of the clauses is exactly 3. Clearly, we must
make sure that the number of occurrences of each variable remains constant. This would complete
the proof of Theorem 1.1.
3.1 Step 1
Before presenting the first step we offer some intuition. In order to make the number of occurrences of
the universal variables constant we replace their occurrences by new and distinct existential variables.
In detail, assume x is a universal variable that occurs ` times in an instance Ψ of ∀∃-3-SAT[1 − ε, 1].
T HEORY OF C OMPUTING, Volume 3 (2007), pp. 45–60 49
I. H AVIV, O. R EGEV, AND A. TA -S HMA
For such a variable we construct the graph G(`) = (U ∪ V ∪ W, E) given in Claim 2.5 and identify its
` output vertices V with the ` new existential variables. In addition, we associate a universal variable
with each of the 2` vertices of U, and an existential variable with each vertex in W and also with each
edge in E. We add clauses that verify that in the subgraph of G(`) given by the edges with value True,
there are ` vertex-disjoint paths from U to V (and hence each vertex in V has one incoming path). We
also add clauses that verify that if an edge has value True then both its endpoints must have the same
value. This guarantees that each variable in V gets the value of one of the variables in U. Completeness
follows because for any assignment to U, we can assign all the variables in V to the same value by
connecting them to those variables in U that get the more popular assignment (recall that |U| = 2|V | and
the properties given in Claim 2.5). For the proof of soundness, we show that if all the U variables are
assigned the same value, then all the V variables should also be assigned this value.
3.1.1 The reduction
The proof is by reduction from the problem ∀∃-3-SAT[1−ε, 1] which is Π2 -hard for some constant ε > 0
as shown in [6]. Let Ψ(X,Y ) be a 3-CNF Boolean formula with m clauses over the set of variables X ∪Y ,
where X = {x1 , . . . , x|X| } is the set of universal variables, and Y = {y1 , . . . , y|Y | } is the set of existential
variables. The reduction constructs a formula Ψ0 (X 0 ,Y 0 ) over X 0 ∪Y 0 . The number of occurrences in Ψ0
of each universal variable from X 0 will be bounded by an absolute constant B, and the number of literals
in each clause will be at most D. In fact, these constants are B = 2 and D = d + 1, where d is given in
Claim 2.5.
For each universal variable xi ∈ X denote by `i the number of its occurrences in the formula Ψ, and
apply Claim 2.5 to obtain the graph Gi = G(`i ) = (Ui ∪ Vi ∪ Wi , Ei ). Recall that the maximum degree
(indegree and outdegree) of these graphs is bounded by some constant d and that the number of edges
in Gi is bounded by c · `i for some constant c. Denote the vertex sets of Gi by
(i) (i) (i) (i) (i) (i)
Vi = {v1 , . . . , v`i }, Ui = {u1 , . . . , u2`i }, and Wi = {w1 , . . . , w|Wi | } ,
(i) (i)
and its edge set by Ei = {e1 , . . . , e|Ei | }. The set of existential variables in Ψ0 is
|X|
!
0
[
Y = (Vi ∪Wi ∪ Ei ) ∪Y .
i=1
S|X|
The set of universal variables in Ψ0 is X 0 = i=1 Ui .
The clauses of Ψ0 are divided into the following five types (see Figure 2).
1. Major clauses: These clauses are obtained from clauses of the formula Ψ, by replacing the jth
occurrence of the universal variable xi with the variable
(i)
v j ∈ Vi
for 1 ≤ i ≤ |X|, 1 ≤ j ≤ `i . The number of clauses of this type is m.
T HEORY OF C OMPUTING, Volume 3 (2007), pp. 45–60 50
O N THE H ARDNESS OF S ATISFIABILITY WITH B OUNDED O CCURRENCES
∀ U
∃
1
2 W
3
4
5+∃ V
Figure 2: An illustration of the reduction for the case ` = 6.
2. Outdegree clauses: These clauses verify that among the directed edges leaving a vertex in Gi , at
most one has value True. For each vertex w, we add the clause
(i) (i)
(¬e j1 ∨ ¬e j2 )
(i) (i)
for each pair of edges e j1 , e j2 leaving w. Each such clause is duplicated d 2 times. The number of
clauses of this type is at most `i · c · d 2 d2 for each i.
(i)
3. Flow clauses: These clauses verify for any vertex w j ∈ Wi that if at least one of its outward edges
(i)
has value True then there exists also an edge entering w j with value True. This is done by adding
a clause of the form
(i) (i) (i)
(¬e j0 ∨ e j1 ∨ · · · ∨ e jd0 )
(i) (i) (i) (i) (i)
for each e j0 leaving w j where e j1 , . . . , e jd0 are all the 0 ≤ d 0 ≤ d edges entering w j . The number
of clauses of this type is at most c · `i for each i.
(i)
4. V -degrees clauses: These clauses verify that each vertex v j has at least one incident edge with
True value. This is done by adding one clause of the form
(i) (i)
(e j1 ∨ · · · ∨ e jd0 )
(i) (i) (i)
where e j1 , . . . , e jd0 are the d 0 ≤ d edges incident to v j . The number of clauses of this type is `i for
each i.
(i) (i) (i)
5. Edge consistency clauses: For each edge e j ∈ Ei do the following. Let w j1 , w j2 ∈ Ui ∪ Vi ∪ Wi
be its endpoints. Add the two clauses
(i) (i) (i) (i) (i) (i)
(¬e j ∨ w j1 ∨ ¬w j2 ) and (¬e j ∨ ¬w j1 ∨ w j2 ) ,
T HEORY OF C OMPUTING, Volume 3 (2007), pp. 45–60 51
I. H AVIV, O. R EGEV, AND A. TA -S HMA
(i) (i) (i)
which check that if the value of e j is True, then w j1 and w j2 have the same truth value. The
number of clauses of this type is at most 2c`i for each i.
Note that each clause contains at most D = d + 1 literals. Using ∑i `i ≤ 3m, the number of clauses in
Ψ0 , which we denote by m0 , is at most O(mc · (d 4 + 1)) ≤ C · m for some absolute constant C. Moreover,
the number of occurrences of each universal variable is exactly 2, because universal variables appear
only in clauses of type (5) and vertices in the Ui have outdegree 1. This completes the construction of
Ψ0 .
3.1.2 Completeness
Our goal in the completeness proof is to show that if Ψ(X,Y ) is a YES instance of ∀∃-3-SAT[1 − ε, 1],
then for any assignment to X 0 , there is an assignment to Y 0 that satisfies all the m0 clauses in Ψ0 (X 0 ,Y 0 ).
S|X|
Let t 0 be an arbitrary assignment to the universal variables X 0 . Recall that X 0 is the union i=1 Ui . We
define an assignment t to X based on the majority of the assignments given by t 0 . More formally,
(
(i)
True, if |{ j : t 0 (u j ) = True}| ≥ `i ,
t(xi ) =
False, otherwise.
By the assumption on the original formula Ψ(X,Y ), the assignment t can be extended to X ∪Y , in a way
that satisfies all the clauses in Ψ(X,Y ). Let us extend the assignment t 0 to the existential variables
|X|
[
Y0 = (Vi ∪Wi ∪ Ei ) ∪Y .
i=1
First, let the assignment t 0 give the same values as t for the variables in Y . For each i denote by Si ⊆ Ui
a set of vertices from Ui of size |Si | = `i in which every variable has value t(xi ). There exists such a set
according to the definition of t. By Claim 2.5 there are `i vertex-disjoint directed paths in Gi from Si to
(i) (i)
Vi . We define t 0 (e j ) to be True if e j appears in one of these paths and False otherwise. In addition, t 0
gives the value t(xi ) to all variables in Vi ∪Wi .
We now check that the assignment t 0 satisfies all clauses in Ψ0 . The assignment to the variables in
Vi is t(xi ). Since the variables Y are also assigned according to t, all clauses of type (1) are satisfied.
The paths given by Claim 2.5 are vertex-disjoint. In particular, every vertex has at most one outward
edge assigned to True, so all clauses of type (2) are satisfied too. Moreover, if at least one of the edges
leaving a vertex w ∈ Wi has value True then there exists also a directed edge with value True entering
w. Therefore, the clauses of type (3) are satisfied. The number of paths in Gi is `i , so there is one
path reaching every vertex in Vi . This means that the clauses of type (4) are satisfied too. Finally, our
assignment gives the value t(xi ) to all variables in Si ∪Vi ∪Wi . In particular, each edge assigned to True
has both its endpoints with the same value. Thus, the clauses of type (5) are satisfied, as required.
3.1.3 Soundness
In the soundness proof we assume Ψ(X,Y ) is a NO instance of ∀∃-3-SAT[1 − ε, 1]. We will show the
existence of an assignment to X 0 for which any assignment to Y 0 satisfies at most (1 − ε 0 )m0 clauses of
Ψ0 (X 0 ,Y 0 ) for ε 0 = ε/C, and hence the theorem will follow.
T HEORY OF C OMPUTING, Volume 3 (2007), pp. 45–60 52
O N THE H ARDNESS OF S ATISFIABILITY WITH B OUNDED O CCURRENCES
Let t be an assignment to X such that every extension of t to X ∪Y satisfies at most (1 − ε)m clauses
(i)
in Ψ(X,Y ). Define an assignment t 0 to X 0 in which every variable u j has the value t(xi ). Extend t 0 to
an assignment to X 0 ∪ Y 0 in an arbitrary way. Our goal in the following is to show that the number of
clauses satisfied by t 0 is at most (1 − ε 0 )m0 . We start with the following two claims.
Claim 3.1. Let t 0 be an assignment to X 0 ∪Y 0 as above. Then t 0 can be modified to an assignment t 00 that
satisfies every clause of type (2) and satisfies at least as many clauses as t 0 satisfies.
Proof. We obtain t 00 by performing the following modification to t 0 for each i: For each variable in Wi , if
it has more than one outward edge assigned to True by t 0 , t 00 assigns False to all its outward edges. Since
we only modify variables in Ei , clauses of type (1) are not affected. Moreover, since we only set edges
to False, we do not decrease the number of satisfied clauses of type (5). We might, however, reduce
the number of satisfied clauses of types (3) and (4) by at most d 2 for each variable (at most d for each
out-neighbor of the vertex). On the other hand, the corresponding clause of type (2) is satisfied by t 00 ,
and by the duplication, this amounts to at least d 2 additional satisfied clauses. In total, the number of
clauses satisfied by t 00 is at least the number of clauses satisfied by t 0 , and the claim follows.
Claim 3.2. Let t 0 be an assignment to X 0 ∪ Y 0 that satisfies all clauses of type (2). Denote by k the
(i) (i)
number of vertices v j ∈ l Vl satisfying t 0 (v j ) 6= t(xi ), where t is the assignment to X as above. Then
S
at least k clauses of types (3), (4) or (5) are unsatisfied by t 0 .
(i) (i)
Proof. Fix some i. It suffices to show that to each vertex v j satisfying t 0 (v j ) 6= t(xi ) we can assign in
a one-to-one fashion a clause of type (3), (4) or (5) which is not satisfied by t 0 . To show this let G0 be
the subgraph of Gi given by the edges assigned to True by t 0 . Let A j be the set of vertices that have a
(i)
directed path in G0 to v j . Since clauses of type (2) are all satisfied by t 0 , the sets A j are pairwise disjoint.
(i)
Fix some 1 ≤ j ≤ `i such that t 0 (v j ) 6= t(xi ). Since Gi is acyclic, A j contains a vertex u whose indegree
(i)
in G0 is 0. If u is in Ui then at least one of the clauses of type (5) on the path from u to v j is unsatisfied
(i)
by t 0 , because t 0 (u) = t(xi ) whereas t 0 (v j ) 6= t(xi ). Otherwise at least one of the clauses of types (3) and
(4) is unsatisfied by t 0 . Therefore, we see that the number of clauses of type (3)-(5) unsatisfied by t 0 is
(i) (i)
at least the number of vertices v j satisfying t 0 (v j ) 6= t(xi ).
(i)
Recall that t 0 is an assignment to X 0 ∪ Y 0 that assigns every variable u j to t(xi ). We have to show
that t 0 satisfies at most (1 − ε 0 )m0 clauses in Ψ0 . By Claim 3.1 we can assume that t 0 satisfies all clauses
of type (2) in Ψ0 .
Now, we define an assignment t 00 to X 0 ∪Y 0 as follows. For each i, let Si be an arbitrary subset of Ui
of size `i . We know that there exist `i directed vertex-disjoint paths from Si to Vi in Gi . The assignment
(i) (i)
t 00 assigns all the e j in these paths to True and all other e j to False. Moreover, t 00 gives all variables in
Ui ∪Vi ∪Wi the value t(xi ). Finally, we define t 00 on Y to be identical to t 0 . Notice that in t 00 all clauses of
(i) (i)
type (2)-(5) are satisfied. Denote by k the number of the variables v j satisfying t 0 (v j ) 6= t(xi ). Then
the number of type (1) clauses satisfied by t 00 is smaller than that of t 0 by at most k. Moreover, t 0 satisfies
all clauses of type (2), so by Claim 3.2 at least k clauses of type (3)-(5) are unsatisfied by t 0 . In total,
the number of clauses satisfied by t 00 is at least the number of clauses satisfied by t 0 .
T HEORY OF C OMPUTING, Volume 3 (2007), pp. 45–60 53
I. H AVIV, O. R EGEV, AND A. TA -S HMA
Finally, by our assumption on Ψ and on t we get that at least εm clauses of type (1) are not satisfied
by t 00 . So the number of satisfied clauses is at most m0 − εm ≤ (1 − ε 0 )m0 , as required.
3.2 Step 2
With Step 1 proven, we now apply an idea of [10] to show that there are absolute constants B and ε > 0,
for which the problem ∀∃-D-SAT-B[1 − ε, 1] is Π2 -hard. This proof uses the expander graphs from
Lemma 2.2.
The reduction: Consider the Π2 -hard problem ∀∃-D-SAT-B∀ [1 − ε 0 , 1] for some ε 0 > 0. Let Ψ(X,Y )
be an instance of this problem. For every existential variable yi ∈ Y (1 ≤ i ≤ |Y |) denote by ni the
number of the occurrences of yi in Ψ. Assuming ni is large enough, consider the graph Gi = (Vi , Ei )
given by Lemma 2.2 for ni , with ni ≤ |Vi | ≤ C1 ni (if ni is not large enough, we do not need to modify
(i) (i)
this variable). Label the vertices of Gi with |Vi | new distinct existential variables Yi = {y1 , . . . , y|Vi | }. We
construct a new Boolean formula Ψ0 (X,Y 0 ) over the universal variables in X and the existential variables
S|Y |
in Y 0 = i=1 Yi . First, for each 1 ≤ i ≤ |Y | replace the occurrences of yi by ni distinct variables of Yi .
(i) (i)
Second, for each edge (y j , y j0 ) in Gi , add to Ψ the two clauses
(i) (i) (i) (i)
(¬y j ∨ y j0 ) and (y j ∨ ¬y j0 ) ,
(i) (i)
which are both satisfied if and only if the variables y j , y j0 have the same value. The number of clauses
in Ψ0 is linear in ∑i ni ≤ Dm. Notice, that the number of occurrences of each variable in Ψ0 is bounded
by a constant.
Correctness: Let Ψ(X,Y ), an m clause formula, be a YES instance, i. e., for every assignment to X
there exists an assignment to Y such that every clause in Ψ is satisfied. Clearly, for any assignment
to X there exists an assignment to Y 0 which satisfies all the clauses in Ψ0 , because we can set the Yi
variables the value of yi in Ψ. Now , assume Ψ is a NO instance, so there is an assignment t to X such
that for any assignment to Y at least ε 0 m clauses are unsatisfied in Ψ. Let t 0 be an arbitrary extension
of t to X ∪Y 0 . If for some 1 ≤ i ≤ |Y |, t 0 does not assign to all the Yi variables the same value for some
1 ≤ i ≤ |Y |, it is possible to improve the number of satisfied clauses by setting all the Yi variables to
the majority vote of t 0 on Yi . Indeed, denote by Si the set of variables in Yi that were assigned by t 0 to
True. This modification reduces the number of satisfied clauses by at most min(|Si |, |Si |), but satisfies at
least |E(Si , Si )| unsatisfied consistency clauses. Lemma 2.2 states that |E(Si , Si )| > min(|Si |, |Si |), so this
modification improves the number of satisfied clauses. Hence, we can assume that for each 1 ≤ i ≤ |Y |,
t 0 assigns to all the Yi variables the same value for each 1 ≤ i ≤ |Y |. Thus, by the assumption on Ψ we
conclude that t 0 does not satisfy at least ε 0 m clauses, meaning at least an ε 0 /D fraction of the clauses is
not satisfied. Defining ε = ε 0 /D completes the proof.
3.3 Step 3
This subsection completes the proof of Theorem 1.1 by showing a reduction that modifies the size of the
clauses to exactly 3.
T HEORY OF C OMPUTING, Volume 3 (2007), pp. 45–60 54
O N THE H ARDNESS OF S ATISFIABILITY WITH B OUNDED O CCURRENCES
The reduction: Let Ψ(X,Y ) be an instance of ∀∃-D-SAT-B[1 − ε 0 , 1] with m clauses. We transform
Ψ into a formula Ψ(X 0 ,Y 0 ), whose clauses are of size exactly 3, as follows. For each clause of size 1,
like (a), we add a new universal variable z and replace it by (a ∨ z ∨ z). Similarly, for each clause of size
2, like (a ∨ b), we add a new universal variable z and replace it by (a ∨ b ∨ z). Now consider a clause
C = (u1 ∨ u2 ∨ · · · ∨ ur ) of size r > 3, where the ui are literals. For each such clause introduce r − 3 new
and distinct existential variables z1 , . . . , zr−3 and replace C in the formula Ψ by the clauses of C0 ,
C0 = (u1 ∨ u2 ∨ z1 ) ∧ (¬z1 ∨ u3 ∨ z2 ) ∧ · · · ∧ (¬zr−4 ∨ ur−2 ∨ zr−3 ) ∧ (¬zr−3 ∨ ur−1 ∨ ur ) .
The number of the clauses in Ψ0 is at most Dm. Obviously, the number of occurrences of each variable
remains the same, and the newly added variables appear either once or twice.
Correctness: It is easy to see that if Ψ is a YES instance then so is Ψ0 and that if Ψ is a NO instance,
then there exists an assignment to X 0 such for any assignment Y 0 , at least ε 0 m of the clauses of Ψ0 (X 0 ,Y 0 )
are unsatisfied. So for ε = ε 0 /D we get the desired result.
4 On the number of occurrences
The output of the reduction of Section 3 is a formula in which every universal variable occurs at most
twice and every existential variable occurs at most B times for some constant B. By performing a
transformation similar to the one in Step 2 with the graphs of Lemma 2.2 replaced by directed cycles,
the number of occurrences of each existential variable can be made at most 3 (see for example Theorem
10.2, Part 1 in [2]). This implies that if we allow each universal variable to occur at most twice and each
existential variable to occur at most 3 times, the problem remains Π2 -hard. Here, we show that 2 and 3
are the best possible constants (unless the polynomial-time hierarchy collapses).
First note that whenever a universal variable occurs only once in a formula, we can remove it without
affecting the formula. Hence, if each universal variable occurs at most once, the problem is in NP and
thus is not Π2 -hard, unless the polynomial-time hierarchy collapses.
Moreover, if we allow every existential variable to occur at most twice, the problem lies in coNP and
is thus unlikely to be Π2 -hard. Given an assignment to the universal variables X, the formula Ψ(X,Y )
becomes a SAT formula in which each variable appears at most twice. Checking satisfiability of such
formulas can be done in polynomial time [13]. Indeed, variables that appear only once and those that
appear twice with the same sign can be removed from the formula together with the clauses that contain
them. This means that we are left with a SAT formula in which each variable appears once as a positive
literal and once as a negative one. So consider the bipartite graph H = (A ∪ B, E) in which A is the set
of clauses of Ψ and B is the set of its existential variables. We connect by an edge a clause in A to a
variable in B if the clause contains the variable. Notice that there exists a matching in H that saturates
A if and only if the formula is satisfiable. The existence of such a matching can be checked easily in
polynomial time. Therefore ∀∃-SAT restricted to instances in which every existential variable occurs at
most twice is in coNP.
T HEORY OF C OMPUTING, Volume 3 (2007), pp. 45–60 55
I. H AVIV, O. R EGEV, AND A. TA -S HMA
5 Extension to higher levels of the hierarchy
As one might expect, Theorem 1.1 can be generalized to any level of the polynomial-time hierarchy. In
this section, we describe in some detail how this can be done. Our aim is to prove the following theorem
(the problems below are the natural extension of ∀∃-3-SAT to higher levels of the hierarchy; see [6]).
Theorem 5.1. For any r ≥ 1 there exists an ε > 0 such that (∀∃)r -3-SAT-B[1 − ε, 1] is Π2r -complete
and ∃(∀∃)r -3-SAT-B[1 − ε, 1] is Σ2r+1 -complete (where B is some absolute constant). Moreover, this is
true even when the number of literals in each clause is exactly 3.
For convenience, we present the proof only for the even levels of the hierarchy (Π2r ). The case of
odd levels is almost identical.
Our starting point is a result of [6], which says that for any r ≥ 1 there exists an ε > 0 such that
(∀∃)r -3-SAT[1 − ε, 1] is Π2r -complete. As in Section 3, the proof proceeds in three steps. In the first
we reduce the number of occurrences of universal variables. In the second we reduce the number of
occurrences of existential variables. Finally, in the third step we modify the formula such that the size
of each clause is exactly 3.
5.1 Step 1
In this step we show that for any ε > 0 there exists an ε 0 > 0 such that (∀∃)r -3-SAT[1 − ε, 1] reduces to
(∀∃)r -D-SAT-B∀ [1 − ε 0 , 1] for some absolute constants D, B (where the latter problem is a restriction of
the former to instances in which each universal variable appears at most B times). In more detail, given
a 3-CNF formula Ψ on variable set X1 ∪Y1 ∪ · · · ∪ Xr ∪Yr , we show how to construct a D-CNF formula
Ψ0 on variable set X10 ∪ Y10 ∪ · · · ∪ Xr0 ∪ Yr0 in which each universal variable appears at most B times, and
whose size is linear in the size of Ψ, such that
max min · · · max min SAT(Ψ,tX1 ,tY1 , . . . ,tXr ,tYr )
tX1 tY1 tXr tYr
= max min · · · max min SAT(Ψ0 ,tX10 ,tY10 , . . . ,tXr0 ,tYr0 ) , (5.1)
tX 0 tY 0 tX 0 tY 0
1 1 r r
where SAT denotes the number of unsatisfied clauses in a formula for a given assignment. It is easy to
see that this is sufficient to establish the correctness of the reduction. Moreover, it can be verified that in
Step 1, Section 3 we proved Equation (5.1) for the case r = 1.
Before describing the reduction, we note that in Step 1, Section 3, the only property of the original
formula that we used is that flipping the value of an occurrence of a variable can change the number
of satisfied clauses by at most one. This leads us to the following lemma, whose proof was essentially
given already in Step 1, Section 3.
Lemma 5.2. For any ` ≥ 1 there exists a k ≥ ` and a D-SAT formula Φ(x1 , . . . , x2` , y1 , . . . , yk ) (for some
absolute constant D) on 2` + k variables of size O(`) in which each of the first 2` variables appears at
most twice such that the following holds. For any integer-valued function f on ` Boolean variables with
the property that flipping any one variable changes the value of f by at most one, we have that
max f (x, . . . , x) = max min ( f (y1 , . . . , y` ) + SAT(Φ, x1 , . . . , x2` , y1 , . . . , yk )) ,
x x1 ,...,x2` y1 ,...,yk
T HEORY OF C OMPUTING, Volume 3 (2007), pp. 45–60 56
O N THE H ARDNESS OF S ATISFIABILITY WITH B OUNDED O CCURRENCES
where x, x1 , . . . , x2` , y1 , . . . , yk are Boolean variables.
Using this lemma we can now describe our reduction. We are given a 3-CNF formula Ψ on variable
set X1 ∪Y1 ∪ · · · ∪ Xr ∪Yr . We perform the following modifications for each universal variable x. Let i be
such that x ∈ Xi and ` be the number of times x occurs in Ψ. Let k and Φ be as given by Lemma 5.2.
First, we replace x ∈ Xi with 2` new variables x1 , . . . , x2` ∈ Xi and add k new variables y1 , . . . , yk to Yi .
Next, we replace the ` occurrences of x with y1 , . . . , y` . Finally, we append Φ(x1 , . . . , x2` , y1 , . . . , yk ) to
the formula. Let Ψ0 be the resulting formula and X10 ∪Y10 ∪ · · · ∪ Xr0 ∪Yr0 be the resulting variable set. This
completes the description of the reduction.
Clearly, each universal variable in Ψ0 appears at most twice, and moreover, the size of Ψ0 is linear in
that of Ψ. Therefore it remains to prove Equation (5.1). We do this by showing that for each universal
variable, the modifications we perform leave the expression in Equation (5.1) unchanged. So let Ψ be an
arbitrary formula on some variable set X1 ∪Y1 ∪ · · · ∪ Xr ∪Yr , and let x ∈ Xi be a universal variable with
` occurrences. It can be seen that our goal is to show that1
max min · · · max max min · · · max min g(tX1 ,tY1 , . . . ,tXi \{x} , x, . . . , x,tYi , . . . ,tXr ,tYr )
tX1 tY1 tXi \{x} x tYi tXr tYr
= max min · · · max max min min · · · max min
tX1 tY1 tXi \{x} x1 ,...,x2` y1 ,...,yk tYi tXr tYr
(g(tX1 ,tY1 , . . . ,tXi \{x} , y1 , . . . , y` ,tYi , . . . ,tXr ,tYr ) + SAT(Φ, x1 , . . . , x2` , y1 , . . . , yk )) ,
where g denotes the number of unsatisfied clauses in Ψ under the given assignment to all variables
except x and to all occurrences of x, and k and Φ are as in Lemma 5.2. Clearly it suffices to prove this
equality for any fixed setting to the variables quantified before x, i. e.,
max min · · · max min g(tX1 ,tY1 , . . . ,tXi \{x} , x, . . . , x,tYi , . . . ,tXr ,tYr )
x tYi tXr tYr
= max min min · · · max min
x1 ,...,x2` y1 ,...,yk tYi tXr tYr
(g(tX1 ,tY1 , . . . ,tXi \{x} , y1 , . . . , y` ,tYi , . . . ,tXr ,tYr ) + SAT(Φ, x1 , . . . , x2` , y1 , . . . , yk )) ,
but this follows from Lemma 5.2.
We conclude that (∀∃)r -D-SAT-B∀ [1 − ε, 1] is Π2r -hard for some ε > 0.
5.2 Step 2
In this step we show that for any ε > 0 there exists an ε 0 > 0 such that (∀∃)r -D-SAT-B∀ [1 − ε, 1] reduces
to (∀∃)r -D-SAT-B[1 − ε 0 , 1] for some absolute constants D, B. The following lemma is the analogue of
Lemma 5.2 for existential variables, and its proof essentially appeared already in Step 2, Section 3.
Lemma 5.3. For any large enough ` there exists a 2-SAT formula Φ(y1 , . . . , y` ) on ` variables of size
O(`) in which each variable appears at most B times (for some absolute constant B) such that the
1 We remark that the fact that we write max
tXi \{x} maxx as opposed to maxx maxtXi \{x} will be crucial when we apply
Lemma 5.2, as this prevents an additional quantifier alternation.
T HEORY OF C OMPUTING, Volume 3 (2007), pp. 45–60 57
I. H AVIV, O. R EGEV, AND A. TA -S HMA
following holds. For any integer-valued function f on ` Boolean variables with the property that flipping
any one variable changes the value of f by at most one, we have that
min f (y, . . . , y) = min ( f (y1 , . . . , y` ) + SAT(Φ, y1 , . . . , y` )) ,
y y1 ,...,y`
where y, y1 , . . . , y` are Boolean variables.
The reduction is as follows. We are given a D-CNF formula Ψ on variable set X1 ∪Y1 ∪ · · · ∪ Xr ∪Yr .
We perform the following modifications for each existential variable y. Let i be such that y ∈ Yi and `
be the number of times y occurs in Ψ. Let Φ be as given by Lemma 5.3. First, we replace y ∈ Yi with
` variables y1 , . . . , y` ∈ Yi . Next, we replace the ` occurrences of y with y1 , . . . , y` . Finally, we append
Φ(y1 , . . . , y` ) to the formula. This completes the description of the reduction. The proof of correctness
is similar to the previous one and uses Lemma 5.3.
5.3 Step 3
To complete the proof of Theorem 5.1 we now modify the formula so that the number of literals in each
clause is exactly 3. Given a formula Ψ on variable set X1 ∪Y1 ∪ · · · ∪ Xr ∪Yr we apply the modification
of Step 3, Section 3. We add the new existential variables to Yr and the new universal variables to Xr .
The proof of correctness is easy and is omitted.
Acknowledgements
We thank Ker-I Ko for sending us a copy of [7]. Some of the early ideas that eventually led us to
the construction of Section 3 were obtained while the second author was working on [4] together with
Daniele Micciancio and Venkatesan Guruswami. We also thank two anonymous referees for their helpful
comments.
References
[1] * N. A LON AND M. C APALBO: Smaller explicit superconcentrators. Internet Math., 1(2):151–
163, 2004. [InternetMath:1(2):151–163]. 2.2, 2.4, 1
[2] * S. A RORA AND C. L UND: Hardness of approximation. In D ORIT S. H OCHBAUM, editor,
Approximation algorithms for NP-hard problems. PWS, Boston, 1996. 3, 4
[3] * O. G ABBER AND Z. G ALIL: Explicit constructions of linear-sized superconcentrators. Jour-
nal of Computer and System Sciences, 22(3):407–420, June 1981. [JCSS:10.1016/0022-
0000(81)90040-4]. 2.2
[4] * V. G URUSWAMI , D. M ICCIANCIO , AND O. R EGEV: The complexity of the covering radius
problem on lattices and codes. Computational Complexity, 14(2):90–121, 2005. Preliminary ver-
sion in CCC’04. [doi:10.1007/s00037-005-0193-y]. 1, 5.3
T HEORY OF C OMPUTING, Volume 3 (2007), pp. 45–60 58
O N THE H ARDNESS OF S ATISFIABILITY WITH B OUNDED O CCURRENCES
[5] * I. H AVIV AND O. R EGEV: Hardness of the covering radius problem on lattices. In Proc. of 21st
Ann. Conf. on Computational Complexity (CCC’06), pp. 145–158. IEEE Computer Society Press,
2006. [CCC:10.1109/CCC.2006.23]. 1
[6] * K.-I. KO AND C.-L. L IN: Non-approximability in the polynomial-time hierarchy. Technical
Report 94-2, Dept. of Computer Science, SUNY at Stony Brook, 1994. 1, 3, 3.1.1, 5, 5
[7] * K.-I. KO AND C.-L. L IN: On the longest circuit in an alterable digraph. J. Global Optimization,
7(3):279–295, 1995. [Springer:k74448w88p1483ww]. 1, 1, 2.1, 3, 5.3
[8] * A. L UBOTZKY, R. P HILLIPS , AND P. S ARNAK: Ramanujan graphs. Combinatorica, 8(3):261–
277, 1988. [Springer:k285687344657q53]. 2.2, 2.2
[9] * G. A. M ARGULIS: Explicit group-theoretic constructions of combinatorial schemes and their
applications in the construction of expanders and concentrators. Problemy Peredachi Informatsii,
24(1):51–60, 1988. 2.2, 2.2
[10] * C. H. PAPADIMITRIOU AND M. YANNAKAKIS: Optimization, approximation, and complexity
classes. Journal of Computer and System Sciences, 43(3):425–440, 1991. [JCSS:10.1016/0022-
0000(91)90023-X]. 1, 3.2
[11] * M. S CHAEFER AND C. U MANS: Completeness in the polynomial-time hierarchy: A com-
pendium. SIGACT News, 33(3):32–49, September 2002. Guest column in Complexity Theory
Column. [SIGACT:10.1145/582475.582484]. 2.1
[12] * M. S CHAEFER AND C. U MANS: Completeness in the polynomial-time hierarchy: Part II.
SIGACT News, 33(4):22–36, December 2002. Guest column in Complexity Theory Column.
[SIGACT:10.1145/601819.601829]. 2.1
[13] * C.A. T OVEY: A simplified NP-complete satisfiability problem. Discrete Applied Mathematics,
8(1):85–89, 1984. [Elsevier:10.1016/0166-218X(84)90081-7]. 4
[14] * V.V. VAZIRANI: Approximation algorithms. Springer-Verlag, Berlin, 2001. 3
AUTHORS
Ishay Haviv [About the author]
School of Computer Science
Tel Aviv University, Tel Aviv, Israel
T HEORY OF C OMPUTING, Volume 3 (2007), pp. 45–60 59
I. H AVIV, O. R EGEV, AND A. TA -S HMA
Oded Regev [About the author]
Assistant professor
School of Computer Science
Tel Aviv University, Tel Aviv, Israel
http://www.cs.tau.ac.il/~odedr
Amnon Ta-Shma [About the author]
Assistant professor
School of Computer Science
Tel Aviv University, Tel Aviv, Israel
http://www.cs.tau.ac.il/~amnon
ABOUT THE AUTHORS
I SHAY H AVIV is a a graduate student at the School of Computer Science, Tel Aviv Uni-
versity, under the supervision of Oded Regev. He is interested in theoretical computer
science, especially the complexity of lattice problems. He also loves animals and acts
for their rights.
O DED R EGEV graduated from Tel Aviv University in 2001 under the supervision of Yossi
Azar. Before joining Tel Aviv University, he spent two years as a postdoctoral fellow at
the Institute for Advanced Study, Princeton, and one year at the University of California,
Berkeley. His research interests include quantum computation, computational aspects
of lattices, and other topics in theoretical computer science. He also enjoys hiking,
running, and photography.
A MNON TA -S HMA graduated from the Hebrew University in 1996 under the supervision of
Noam Nisan. Before joining Tel Aviv University, he spent three years as a postdoctoral
fellow at the International Computer Science Institute, Berkeley and the University of
California, Berkeley. His research interests include the role of randomness in compu-
tation, quantum computation, and other topics in theoretical computer science. He also
enjoys his family and thanks them for their love.
T HEORY OF C OMPUTING, Volume 3 (2007), pp. 45–60 60