14
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ 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) $\endgroup$
    – D.W. ♦
    Jun 22, 2015 at 19:43
  • $\begingroup$ 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. $\endgroup$
    – vzn
    Jun 22, 2015 at 22:51
  • $\begingroup$ 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.... $\endgroup$
    – vzn
    Jun 23, 2015 at 5:19
  • $\begingroup$ see also wikipedia/ NPI / Ladners thm $\endgroup$
    – vzn
    Jun 23, 2015 at 15:25

1 Answer 1

Reset to default
14
$\begingroup$

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

Improve this answer
$\endgroup$
3
  • $\begingroup$ awesome but what exactly is SAT(S)? plz flesh this out more (although admittedly/ clearly few others think it necessary!) $\endgroup$
    – vzn
    Jun 22, 2015 at 22:50
  • $\begingroup$ This is explained very clearly in the Wikipedia page on Schaefer's theorem, from which I copied this notation. $\endgroup$
    – Yuval Filmus
    Jun 22, 2015 at 23:05
  • 1
    $\begingroup$ but anyway still think this could all be explained better. "Schaefer defines a decision problem that he calls the Generalized Satisfiability problem". but apparently it is not so Generalized then....? eg why is the language he studies important, and not contrived? is it used anywhere else in CS other than his paper? what are the larger implications of this theorem, are there any or is it an isolated curiosity that seems to lead nowhere? could it conceivably somehow be used in a P vs NP attack or not? etc $\endgroup$
    – vzn
    Jun 22, 2015 at 23:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.