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.