Volume 3 (2007) Article 3 pp. 45-60

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

by Ishay Haviv, Oded Regev, and Amnon Ta-Shma

Received: July 28, 2006
Published: March 28, 2007

$\newcommand{\myminus}{–} \newcommand{\eps}{\epsilon} \newcommand{\NP}{\mathsf{NP}} \newcommand{\YES}{\mathsf{YES}} \newcommand{\NO}{\mathsf{NO}} \newcommand{\Bsat}{{\mathsf{B}}} \newcommand{\threesat}{\rm{3}\myminus\mathsf{SAT}} \newcommand{\threesatB}{\rm{3}\myminus\mathsf{SAT}\myminus\Bsat} \newcommand{\gapthreesat}{\mathsf{\forall\exists}\myminus{\rm{3}}\myminus\mathsf{SAT}} \newcommand{\gapKthreesatB}{{(\forall\exists)}^r\myminus{\rm{3}}\myminus{\mathsf{SAT}}\myminus\Bsat} \newcommand{\EgapKthreesatB}{\mathsf{\exists(\forall\exists)}^r\myminus{\rm{3}}\myminus\mathsf{SAT}\myminus\Bsat} \newcommand{\gapKDsatB}{{(\forall\exists)}^r\myminus{\rm{\Dsat}}\myminus{\mathsf{SAT}}\myminus\Bsat} \newcommand{\gapthreesatB}{\mathsf{\forall\exists}\myminus{\rm{3}}\myminus\mathsf{SAT}\myminus\Bsat} \newcommand{\gapDsatB}{\mathsf{\forall\exists}\myminus\rm{\Dsat}\myminus\mathsf{SAT}\myminus\Bsat} \newcommand{\gapDEsatB}{\mathsf{\forall\exists}\myminus\rm{\mathsf{E}\Dsat}\myminus\mathsf{SAT}\myminus\Bsat} \newcommand{\gapEthreesatB}{\mathsf{\forall\exists}\rm{\myminus\mathsf{E}3\myminus}\mathsf{SAT}\myminus\Bsat} \newcommand{\gapDsatBX}{\mathsf{\forall\exists}\myminus\rm{\Dsat}\myminus\mathsf{SAT}\myminus\Bsat_\forall} \newcommand{\gapthreesatBX}{\mathsf{\forall\exists}\myminus\rm{3}\myminus\mathsf{SAT}\myminus\Bsat_\forall}$

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.

DOI: 10.4086/toc.2007.v003a003

© 2007 Ishay Haviv, Oded Regev, and Amnon Ta-Shma
Licensed under a Creative Commons License