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

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.

• Closely related: cs.stackexchange.com/q/42544/755 (read the answers before trying to understand all of the details of the question; the answers are relatively self-contained)
– D.W.
Jun 22 '15 at 19:43
• have wondered about this myself before thx so much for asking! the trick is that schaefers thm is not actually stating that there are no intermediate languages "between" P/NP, it is more subtle. also, try studying the class NPI, aka NP intermediate, there are many refs on Theoretical Computer Science. many major problems are "in" NPI, the two top/ famous ones are factoring and graph isomorphism.
– vzn
Jun 22 '15 at 22:51
• in short Shaefer thm sounds like a thm about SAT but is actually about a narrow language related to SAT which is apparently neither NP hard nor NP complete....? have long been looking for an "undergrad textbook" level presentation of Shaefer thm....
– vzn
Jun 23 '15 at 5:19
– vzn
Jun 23 '15 at 15:25

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$.