Gap theorems for robust satisfiability: Boolean CSPs and beyond

Abstract

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 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 SAT variants is a notable particular case. Universal algebraic methods have been central to recent efforts in classifying the complexity of constraint satisfaction problems...