On the Hardness of Satisfiability with Bounded Occurrences in the Polynomial-Time Hierarchy

Abstract

In 1991, Papadimitriou and Yannakakis gave a reduction implying the $\NP$-hardness of approximating the problem $\threesat$ 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 $\gapthreesat$ in which every variable occurs at most $\Bsat$ times (for some absolute constant $\Bsat$), 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-\eps$ fraction of the clauses. We also generalize this result to any level of the polynomial-time hierarchy.

Published in Theory of Computing, Volume 3 (2007), Article 3; Received: July 28, 2006, Published: March 28, 2007