  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 $\mathbf{NP}$-complete. Schaefer's original dichotomy for
$\textsf{SAT}$ 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.
