2016/10/29 by Ham, Lucy
#05C60 #08A35 #68Q15 #68R01 #Combinatorics (math.CO) #Computational Complexity (cs.CC) #F.1.3 #FOS: Computer and information sciences #FOS: Mathematics #Logic (math.LO)
paper · doi:10.48550/arxiv.1610.09574
A computational problem exhibits a "gap property" when there is no tractable boundary between two disjoint sets of instances. We establish a Gap Trichotomy Theorem for a family of constraint problem variants, completely classifying the complexity of possible \bf NP-hard gaps in the case of Boolean domains. As a consequence, we obtain a number of dichotomies for the complexity of specific variants of the constraint satisfaction problem: all are either polynomial-time tractable or NP-complete. Schaefer's original dichotomy for \textsfSAT variants is a notable particular case. Universal algebraic methods have been central to recent efforts in classifying the complexity of constraint satisfaction problems. A second contribution of the article is to develop aspects of the algebraic approach in the context of a number of variants of the constraint satisfaction problem. In particular, this allows us to lift our results on Boolean domains to many templates on non-Boolean domains.