A gap trichotomy for Boolean constraint problems: extending Schaefer's Theorem

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 variant…