Volume 3 (2007)
Article 3 pp. 45-60
On the Hardness of Satisfiability with Bounded Occurrences in the Polynomial-Time Hierarchy
Received: July 28, 2006
Published: March 28, 2007
Keywords: satisfiability, polynomial-time hierarchy, expander graphs, superconcentrator graphs
ACM Classification: F.1.3
AMS Classification: 03D15, 68Q17
Abstract:
[Plain Text Version]
$
\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.