Why do Shaefer's and Mahaney's Theorems not imply P = NP?

Problem Detail: 

I'm sure someone has thought about this before or immediately dismissed it, but why does Schaefer's dichotomy theory along with Mahaney's theorem on sparse sets not imply P = NP ?

Here's my reasoning: Create a language $L$ which is equal to SAT intersected by an infinite decidable sparse set. Then $L$ must also be sparse. Since $L$ it is not trivial, affine, 2-sat, or Horn-sat, by Shaefer's theorem it must be NP-complete. But then we have a sparse NP-complete set so by Mahaney's theorem, P=NP.

Where am I going wrong here? I suspect that I am misunderstanding/misapplying Shaefer's theorem but I don't see why.

Asked By : Ari

Answered By : Yuval Filmus

Schaefer's theorem applies only to a specific type of languages, those of the form $\mathrm{SAT}(S)$ for a finite set of relations over the Boolean domain or $\mathrm{CSP}(\Gamma)$ for a finite constraint language over the Boolean domain (the two notations are equivalent; see the Wikipedia page for a description). Any other language is not covered by the theorem, and the theorem has nothing to say about it. In particular, Schaefer's theorem doesn't say anything about your language $L$.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/43830