  We study the complexity of SAT($\Gamma$) problems for potentially infinite
languages $\Gamma$ closed under variable negation (sign-symmetric languages).
Via an algebraic connection, this reduces to the study of restricted partial
polymorphisms of $\Gamma$ we refer to as \emph{pSDI-operations} (for partial,
self-dual and idempotent). First, we study the language classes themselves. We
classify the structure of the least restrictive pSDI-operations, corresponding
to the most powerful languages $\Gamma$, and find that these operations can be
divided into \emph{levels}, corresponding to a rough notion of difficulty; and
that within each level there is a strongest operation (the partial $k$-NU
operation, preserving $(k-1)$-SAT) and a weakest operation (the $k$-universal
operation $u_k$, preserving problems definable via bounded-degree polynomials).
We show that every sign-symmetric $\Gamma$ not preserved by $u_k$ implements
all $k$-clauses; thus if $\Gamma$ is not preserved by $u_k$ for any $k$, then
SAT($\Gamma$) is trivially SETH-hard and cannot be solved faster than
$O^*(2^n)$ unless SETH fails.
  Second, we study upper and lower bounds for SAT($\Gamma$) for such languages.
We show that several classes in the hierarchy correspond to problems which can
be solved faster than $2^n$ using previously known algorithmic strategies such
as Subset Sum-style meet-in-the-middle and fast matrix multiplication.
Furthermore, if the sunflower conjecture holds for sunflowers with k sets, then
the partial k-NU language has an improved algorithm via local search.
Complementing this, we show that for every class there is a concrete lower
bound $c$ such that SAT($\Gamma$) cannot be solved faster than $O^*(c^n)$ for
all problems in the class unless SETH fails. This gives the first known case of
a SAT-problem which simultaneously has non-trivial upper and lower bounds under
SETH.
