HiveBrain v1.2.0
Get Started
← Back to all entries
principleModerate

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

Submitted by: @import:stackexchange-cs··
0
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.

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.