Warum implizieren die Sätze von Shaefer und Mahaney nicht P = NP?

14

Ich bin sicher, jemand hat darüber nachgedacht oder es sofort verworfen, aber warum impliziert Schäfers Dichotomietheorie zusammen mit Mahaneys Theorem über spärliche Mengen nicht P = NP?

Hier ist meine Argumentation: Erstellen Sie eine Sprache die SAT entspricht und von einer unendlichen, entscheidbaren, spärlichen Menge durchschnitten wird. Dann muss auch dünn sein. Da nach Shaefers Theorem nicht trivial, affin, 2-Sat oder Horn-Sat ist, muss es NP-vollständig sein. Aber dann haben wir eine spärliche NP-Komplettmenge, so nach Mahaneys Theorem, P = NP.LLL

Wo gehe ich hier falsch? Ich vermute, dass ich Shaefers Satz falsch verstehe / falsch anwende, aber ich verstehe nicht warum.

Ari
quelle
1
Eng verbunden: cs.stackexchange.com/q/42544/755 (lesen Sie die Antworten, bevor Sie versuchen, alle Details der Frage zu verstehen; die Antworten sind relativ in sich geschlossen)
DW
Ich habe mich schon vorher darüber gewundert, dass ich darum gebeten habe! Der Trick ist, dass Schaefers nicht wirklich sagt, dass es keine Zwischensprachen "zwischen" P / NP gibt, es ist subtiler. Versuchen Sie auch, die Klasse NPI, auch bekannt als NP Intermediate, zu studieren. Es gibt viele Quellen zur theoretischen Informatik . Viele Hauptprobleme sind "in" NPI, die beiden bekanntesten sind Factoring und Graph Isomorphism.
vzn
kurz gesagt, Shaefer thm klingt wie ein Thm über SAT, handelt aber eigentlich von einer engen Sprache in Bezug auf SAT, die anscheinend weder NP-schwer noch NP-vollständig ist ...?
Ich
siehe auch wikipedia / NPI / Ladners thm
vzn 23.06.15

Antworten:

13

Schaefers Theorem gilt nur für einen bestimmten Typ von Sprachen, die die Form für eine endliche Menge von Beziehungen über die Boolesche Domäne oder C S P ( Γ ) für eine endliche Beschränkungssprache über die Boolesche Domäne (die beiden) haben Notationen sind äquivalent ( eine Beschreibung finden Sie auf der Wikipedia-Seite ). Jede andere Sprache wird vom Theorem nicht abgedeckt, und der Theorem hat nichts dazu zu sagen. Insbesondere sagt der Satz von Schaefer nichts über Ihre Sprache L aus .SAT(S)CSP(Γ)L

Yuval Filmus
quelle
genial aber was genau ist SAT (S)? plz fleisch dies mehr aus (obwohl zugegebenermaßen / eindeutig wenige andere denken, dass es notwendig ist!)
vzn
Dies wird auf der Wikipedia-Seite zu Schaefers Theorem, von der ich diese Notation kopiert habe, sehr deutlich erklärt.
Yuval Filmus
1
aber trotzdem denke immer noch, dass dies alles besser erklärt werden könnte. "Schaefer definiert ein Entscheidungsproblem, das er das Generalized Satisfiability Problem nennt". aber anscheinend ist es dann nicht so verallgemeinert ....? zB warum ist die Sprache, die er lernt, wichtig und nicht erfunden? Wird es anderswo in CS verwendet als in seiner Zeitung? Was sind die größeren Implikationen dieses Theorems, gibt es irgendwelche oder ist es eine isolierte Neugier, die nirgendwohin zu führen scheint? Könnte es möglicherweise irgendwie in einem P-gegen-NP-Angriff eingesetzt werden oder nicht? etc
vzn