principleModerate
Why do Shaefer's and Mahaney's Theorems not imply P = NP?
Viewed 0 times
theoremswhyimplyshaefermahaneyandnot
Problem
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.
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.
Solution
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$.
Context
StackExchange Computer Science Q#43830, answer score: 14
Revisions (0)
No revisions yet.