Pourquoi les théorèmes de Shaefer et Mahaney n'impliquent-ils pas P = NP?

Je suis sûr que quelqu'un a pensé à cela avant ou immédiatement rejeté, mais pourquoi la théorie de la dichotomie de Schaefer avec le théorème de Mahaney sur les ensembles clairsemés n'implique-t-elle pas P = NP?

Voici mon raisonnement: créer un langage qui est égal à SAT intersecté par un ensemble clairsemé décidable infini. Alors L doit aussi être clairsemé. Puisque L n'est pas trivial, affine, 2-sat ou Horn-sat, selon le théorème de Shaefer, il doit être NP-complet. Mais alors nous avons un ensemble NP-complet clairsemé donc par le théorème de Mahaney, P = NP.$L$$L$$L$

Où vais-je mal ici? Je soupçonne que je comprends mal / applique mal le théorème de Shaefer mais je ne vois pas pourquoi.

Le théorème de Schaefer applique uniquement à un type spécifique de langues, celles de la forme pour un ensemble fini de relations sur le domaine booléenne ou C S P ( Γ ) pour un langage de contrainte finie sur le domaine Boolean (les deux les notations sont équivalentes; voir la page Wikipedia pour une description). Tout autre langage n'est pas couvert par le théorème, et le théorème n'a rien à dire à ce sujet. En particulier, le théorème de Schaefer ne dit rien au sujet de votre langue L .$\mathrm{SAT}(S)$$\mathrm{CSP}(\Gamma)$$L$