Alladi Ramakrishnan Hall

(2+eps)-SAT is NP-hard, and further results on promise constraint satisfaction

Venkat Guruswami

CMU

Given a k-SAT instance with the promise that there is an assignment satisfying at least t out of k literals in each clause, can one efficiently find a satisfying assignment (setting at least one literal to true in every clause)?

Extensions of some 2-SAT algorithms solve this problem when t >= k/2. We prove that for t < k/2, the problem is NP-hard (joint work with P. Austrin and J. Håstad). Thus, SAT becomes hard when the promised density of true literals falls below 1/2. One might thus say that the transition from easy to hard in 2-SAT vs. 3-SAT takes place just after two and not just before three.

The talk will sketch the proof of this hardness result, which is based on the fact that the only functions passing a natural "dictatorship test" are "juntas" depending on few variables. We will also elucidate the general principle, based on the paucity of "weak polymorphisms,” that underlies the intractability of promise constraint satisfaction problems (PCSP), a very general class which includes the above example among many other fundamental problems. We will describe some recent and ongoing work (with J. Brakensiek) that applies this framework to prove new hardness results for approximate graph coloring and establish a complexity dichotomy for the case of Boolean symmetric PCSP.