depending on the nature of relations in S, SAT (S) is either in P or NP-complete. A similar
result holds for generalized satisfiability with constants SAT_ {C}(S)(the version of the above
problem where constants are allowed). We study the possibility to obtain a version of
Schaefer's dichotomy theorem for instances satisfying an additional constraint, namely each
variable appears at most twice. We prove several partial results on the complexity of the …