DocumentCode :
180719
Title :
(2 + epsilon)-Sat Is NP-Hard
Author :
Austrin, Per ; Hastad, Johan ; Guruswami, Venkatesan
Author_Institution :
Sch. of Comput. Sci. & Commun., KTH R. Inst. of Technol., Stockholm, Sweden
fYear :
2014
fDate :
18-21 Oct. 2014
Firstpage :
1
Lastpage :
10
Abstract :
We prove the following hardness result for anatural promise variant of the classical CNF-satisfiabilityproblem: Given a CNF-formula where each clause has widthw and the guarantee that there exists an assignment satisfyingat least g = [w/2] - 1 literals in each clause, it is NP-hard tofind a satisfying assignment to the formula (that sets at leastone literal to true in each clause). On the other hand, when g = [w/2], it is easy to find a satisfying assignment via simplegeneralizations of the algorithms for 2-SAT. Viewing 2-SAT ∈ 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 resultshows, for any fixed ε > 0, the hardness of finding a satisfyingassignment to instances of "(2 + ε)-SAT" where the density ofsatisfied literals in each clause is promised to exceed 1/(2+ε). We also strengthen the results to prove that given a (2k + 1)-uniform hypergraph that can be 2-colored such that each edgehas perfect balance (at most k + 1 vertices of either color), itis NP-hard to find a 2-coloring that avoids a monochromaticedge. In other words, a set system with discrepancy 1 is hard todistinguish from a set system with worst possible discrepancy.
Keywords :
computational complexity; graph theory; (2 + ε)-SAT; CNF-formula; CNF-satisfiability problem; NP-hard problem; NP-hardness; monochromatic edge; uniform hypergraph; Color; Complexity theory; Computer science; Labeling; Polynomials; Probabilistic logic; Standards; Constraint satisfaction; complexity dichotomy; discrepancy; polymorphisms; probabilistically checkable proofs; promise problems;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Foundations of Computer Science (FOCS), 2014 IEEE 55th Annual Symposium on
Conference_Location :
Philadelphia, PA
ISSN :
0272-5428
Type :
conf
DOI :
10.1109/FOCS.2014.9
Filename :
6978984
Link To Document :
بازگشت