All reports by Author Per Austrin:

__
TR13-159
| 20th November 2013
__

Per Austrin, Venkatesan Guruswami, Johan HÃ¥stad#### $(2+\epsilon)$-SAT is NP-hard

Revisions: 2

Per Austrin, Venkatesan Guruswami, Johan HÃ¥stad

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