(2+ε)-SAT is NP-hard
Per Austrin · Open Collections · 2015
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 exis ...