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

by Per Austrin, Venkatesan Guruswami, and Johan Hastad

The cryptic title refers to a nicer articulation of the assertion that 3-SAT is NP-Hard because 3 is the smallest integer greater than 2. That is, if one considers the promise problem of distinguishing $(2g+1)$-CNF that have an assignment that satisfies at least $g$ literals in each clause from $(2g+1)$-CNF that are unsatisfied, then this problem is NP-hard.
The above promise problem has an approximation flavor if one thinks of the promise as a quantitative relaxation (on the strength'' of satisfiability rather than on the fraction of clauses satisfied). As such it may not be that surprising that this NP-hardness result is established by using a non-approximability result (for Label Cover) and that it implies a new non-approximability result (for hereditary discrepancy of matrices'').