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

摘要

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).