ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #2 to TR13-159 | 12th April 2017 18:21

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

RSS-Feed




Revision #2
Authors: Per Austrin, Venkatesan Guruswami, Johan Håstad
Accepted on: 12th April 2017 18:21
Downloads: 10
Keywords: 


Abstract:

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 = \lceil \frac{w}{2}\rceil -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 = \lceil \frac{w}{2}\rceil$, it is easy to find a satisfying assignment via simple generalizations of the algorithms for 2-SAT.

Viewing 2-SAT $\in \mathrm{P}$ as easiness of SAT when $1$-in-$2$ literals are true in every clause, and NP-hardness of 3-SAT as intractability of SAT when $1$-in-$3$ literals are true, our result can be viewed as showing, for every $\epsilon > 0$, intractability of finding a satisfying assignment to instances of "$(2+\epsilon)$-SAT" where the density of satisfied literals in each clause is $1/(2+\epsilon)$.

We also strengthen the results to prove that given a $(2k+1)$-uniform hypergraph that can be 2-colored such that each edge has perfect balance (at most $k+1$ vertices of either color), it is NP-hard to find a 2-coloring that avoids a monochromatic edge. In other words, a set system with discrepancy $1$ is hard to distinguish from a set system with worst possible discrepancy.

Finally, we prove a general result showing intractability of promise CSPs in the wake of paucity of certain "weak polymorphisms." The core of the above hardness results is the claim that weak polymorphisms in these particular cases are juntas depending on few variables.



Changes to previous version:

Several editorial changes; this is the final journal version to appear in SIAM J. Computing (before copy editing).


Revision #1 to TR13-159 | 3rd April 2014 16:19

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


Abstract:

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 = \lceil \frac{w}{2}\rceil -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 = \lceil \frac{w}{2}\rceil$, it is easy to find a satisfying assignment via simple generalizations of the algorithms for 2-SAT.

Viewing 2-SAT $\in \mathrm{P}$ as easiness of SAT when $1$-in-$2$ literals are true in every clause, and NP-hardness of 3-SAT as intractability of SAT when $1$-in-$3$ literals are true, our result can be viewed as showing, for every $\epsilon > 0$, intractability of finding a satisfying assignment to instances of "$(2+\epsilon)$-SAT" where the density of satisfied literals in each clause is $1/(2+\epsilon)$.

We also strengthen the results to prove that given a $(2k+1)$-uniform hypergraph that can be 2-colored such that each edge has perfect balance (at most $k+1$ vertices of either color), it is NP-hard to find a 2-coloring that avoids a monochromatic edge. In other words, a set system with discrepancy $1$ is hard to distinguish from a set system with worst possible discrepancy.

Finally, we prove a general result showing intractability of promise CSPs based on the of paucity of certain "weak polymorphisms." The core of the above hardness results is the claim that weak polymorphisms in these particular cases are juntas depending on few variables.



Changes to previous version:

Several minor editorial changes.


Paper:

TR13-159 | 20th November 2013 15:48

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


Abstract:

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 = \lceil \frac{w}{2}\rceil -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 = \lceil \frac{w}{2}\rceil$, it is easy to find a satisfying assignment via simple generalizations of the algorithms for 2-SAT.

Viewing 2-SAT $\in \mathrm{P}$ as easiness of SAT when $1$-in-$2$ literals are true in every clause, and NP-hardness of 3-SAT as intractability of SAT when $1$-in-$3$ literals are true, our result can be viewed as showing, for every $\epsilon > 0$, intractability of finding a satisfying assignment to instances of "$(2+\epsilon)$-SAT" where the density of satisfied literals in each clause is $1/(2+\epsilon)$.

We also strengthen the results to prove that given a $(2k+1)$-uniform hypergraph that can be 2-colored such that each edge has perfect balance (at most $k+1$ vertices of either color), it is NP-hard to find a 2-coloring that avoids a monochromatic edge. In other words, a set system with discrepancy $1$ is hard to distinguish from a set system with worst possible discrepancy.

Finally, we prove a general result showing intractability of promise CSPs in the wake of paucity of certain "weak polymorphisms." The core of the above hardness results is the claim that weak polymorphisms in these particular cases are juntas depending on few variables.



ISSN 1433-8092 | Imprint