Theory of Computing
-------------------
Title : On the Hardness of Satisfiability with Bounded Occurrences in the Polynomial-Time Hierarchy
Authors : Ishay Haviv, Oded Regev, and Amnon Ta-Shma
Volume : 3
Number : 3
Pages : 45-60
URL : http://www.theoryofcomputing.org/articles/v003a003
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 (forall)(exists)-3-SAT
in which every variable occurs at most B times (for some absolute
constant B), it is Pi_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-epsilon) fraction of
the clauses. We also generalize this result to any level of the
polynomial-time hierarchy.