$(2+epsilon)$-SAT is NP-hard

摘要

We prove the following hardness result for a natural promise variant of the classical CNF-satisfiability problem: Given a CNF-formula where each clause has width w and the guarantee that there exists an assignment satisfying at least g=2w?1 literals in each clause, it is NP-hard to find a satisfying assignment to the formula (that sets at least one literal to true in each clause). On the other hand, when g=2w, it is easy to find a satisfying assignment via simple generalizations of the algorithms for 2-SAT.