Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR99-043 | 5th November 1999 00:00

The Approximability of Set Splitting Problems and Satisfiability Problems with no Mixed Clauses


Authors: Venkatesan Guruswami
Publication: 15th November 1999 17:31
Downloads: 1976


We prove hardness results for approximating set splitting problems and
also instances of satisfiability problems which have no ``mixed'' clauses,
i.e all clauses have either all their literals unnegated or all of them
negated. Recent results of Hastad imply tight hardness results for set
splitting when all sets have size exactly $k \ge 4$ elements and also for
non-mixed satisfiability problems with exactly $k$ literals in each clause
for $k \ge 4$. We consider the problem Max E3-Set Splitting in which sets
have size exactly 3, and prove, by constructing simple gadgets from
3-parity constraints, that Max E3-Set Splitting is hard to approximate
within any factor strictly better than 21/22. We prove that even
satisfiable instances of Max E3-Set Splitting are NP-hard to approximate
better than 27/28; this latter result uses a recent PCP construction of
\cite{GLST98}. We also give a PCP construction which is a variant of the
one in \cite{GLST98} and use it to prove a hardness result of
$11/12+\epsilon$ for approximating non-mixed Max 3Sat, and also a hardness
of $15/16+\epsilon$ for the version where each clause has exactly three
literals (as opposed to up to three literals).

ISSN 1433-8092 | Imprint