Received: July 28, 2006
Published: March 28, 2007
DOI: 10.4086/toc.2007.v003a003
Abstract: [Plain Text Version]
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
variables 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 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.