期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：1999
卷号：1999
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：The label-cover problem was introduced in \cite{ABSS} and shown
there to be quasi-NP-hard to approximate to within a factor of
2log1−n for any {\em constant} 0. This
combinatorial graph problem has been utilized \cite{ABSS,GM,ABMP}
for showing hardness-of-approximation of numerous problems. We
present a direct combinatorial reduction from low
error-probability PCP \cite{DFKRS} to label-cover. This
improves on \cite{ABSS} in two ways. First, it improves the
previous hardness-of-approximation factor known for label-cover,
achieving a factor of 2log1−n where
=1loglogcn for any constant c12 . Furthermore, we
show approximating label-cover is NP-hard for these large
factors, compared to the {\em quasi} NP-hardness, obtained
previously.
Our result for label-cover immediately strengthens the known
hardness result for several approximation problems as mentioned
above, for example the Minimum-Monotone-Satisfying-Assignment
(MinMonSAT) problem \cite{ABMP}. Furthermore, we examine a hierarchy
of approximation problems obtained by restricting the depth of the
monotone formula in MinMonSAT. This hierarchy turns out to be
equivalent to an AND/OR scheduling hierarchy suggested in
\cite{GM}. We show some hardness results for certain levels in this
hierarchy, and place label-cover between levels 3 and 4. This
partially answers an open problem from \cite{GM} regarding the
precise complexity of each level in the hierarchy, and the place of
label-cover in it.
