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 : https://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.