Schaefers Dichotomiesatz

Schaefers Dichotomie-Theorem in der Berechnungskomplexitätstheorie, ein Zweig der Informatik, Das Dichotomie-Theorem von Schaefer gibt notwendige und hinreichende Bedingungen an, unter denen eine endliche Menge S von Beziehungen über dem Booleschen Bereich Polynomialzeit- oder NP-vollständige Probleme ergibt, wenn die Beziehungen von S verwendet werden, um einige der Satzvariablen einzuschränken.[1] Es wird als Dichotomie-Theorem bezeichnet, da die Komplexität des durch S definierten Problems entweder in P oder NP-vollständig ist, im Gegensatz zu einer der Klassen mit mittlerer Komplexität, von denen bekannt ist, dass sie existieren (unter der Annahme P ≠ NP) nach dem Satz von Ladner.

Sonderfälle des Dichotomiesatzes von Schaefer umfassen die NP-Vollständigkeit von SAT (das boolesche Erfüllbarkeitsproblem) und seine beiden beliebten Varianten 1-in-3 SAT und nicht alle gleich 3SAT (oft mit NAE-3SAT bezeichnet). In der Tat, für diese beiden Varianten von SAT, Schaefers Dichotomie-Theorem zeigt, dass ihre monotonen Versionen (wobei Negationen von Variablen nicht erlaubt sind) sind ebenfalls NP-vollständig.

Inhalt 1 Originalpräsentation 2 Moderne Präsentation 3 Eigenschaften von Polymorphismen 4 Verallgemeinerungen 5 Verwandte Arbeit 6 Siehe auch 7 References Original presentation Schaefer defines a decision problem that he calls the Generalized Satisfiability problem for S (bezeichnet mit SAT(S)), wo {Anzeigestil S={R_{1},Punkte ,R_{m}}} ist eine endliche Menge von Beziehungen über Satzvariablen. Ein Beispiel für das Problem ist eine S-Formel, d.h. eine Konjunktion von Einschränkungen des Formulars {Anzeigestil R_{j}(x_{ich_{1}},Punkte ,x_{ich_{n}})} wo {Anzeigestil R_{j}in s} und die {Anzeigestil x_{ich_{j}}} sind Satzvariablen. Das Problem besteht darin, festzustellen, ob die gegebene Formel erfüllbar ist, mit anderen Worten, wenn den Variablen Werte zugewiesen werden können, so dass sie alle Bedingungen erfüllen, die durch die Beziehungen von S gegeben sind.

Schaefer identifiziert sechs Klassen von Sätzen boolescher Beziehungen, für die SAT(S) in P ist und beweist, dass alle anderen Mengen von Relationen ein NP-vollständiges Problem erzeugen. Ein endlicher Satz von Beziehungen S über dem Booleschen Bereich definiert ein in Polynomzeit berechenbares Erfüllbarkeitsproblem, wenn eine der folgenden Bedingungen zutrifft: alle Relationen, die nicht ständig falsch sind, sind wahr, wenn alle ihre Argumente wahr sind; alle Relationen, die nicht ständig falsch sind, sind wahr, wenn alle ihre Argumente falsch sind; alle Relationen sind äquivalent zu einer Konjunktion binärer Klauseln; alle Relationen sind äquivalent zu einer Konjunktion von Hornsätzen; alle Relationen sind äquivalent zu einer Konjunktion von Dual-Horn-Klauseln; alle Relationen sind äquivalent zu einer Konjunktion affiner Formeln. [2] Andernfalls, das Problem SAT(S) ist NP-vollständig.

Modern presentation A modern, Eine vereinfachte Darstellung des Satzes von Schaefer findet sich in einem erläuternden Papier von Hubie Chen.[3][4] In modernen Begriffen, das Problem SAT(S) wird als ein Einschränkungserfüllungsproblem über den booleschen Bereich angesehen. In dieser Gegend, es ist üblich, die Menge der Relationen mit Γ und das durch Γ definierte Entscheidungsproblem als CSP zu bezeichnen(C).

Dieses moderne Verständnis verwendet Algebra, im Speziellen, universelle Algebra. Für den Dichotomiesatz von Schaefer, Das wichtigste Konzept in der universellen Algebra ist das eines Polymorphismus. Eine Operation {Anzeigestil f:D^{m}zu D} ist ein Polymorphismus einer Relation {Anzeigestil Rsubseteq D^{k}} wenn, für jede Auswahl von m Tupeln {Anzeigestil (t_{11},Punktec ,t_{1k}),Punktec ,(t_{m1},Punktec ,t_{mk})} von R, es gilt, dass das Tupel aus diesen m Tupeln erhalten wird, indem f koordinatenweise angewendet wird, d.h. {Anzeigestil (f(t_{11},Punktec ,t_{m1}),Punktec ,f(t_{1k},Punktec ,t_{mk}))} , ist in R. Das ist, eine Operation f ist ein Polymorphismus von R, falls R abgeschlossen ist unter f: Die Anwendung von f auf beliebige Tupel in R ergibt ein weiteres Tupel innerhalb von R. Eine Menge von Relationen Γ hat einen Polymorphismus f, wenn jede Relation in Γ f als Polymorphismus hat. Diese Definition ermöglicht die algebraische Formulierung des Dichotomiesatzes von Schaefer.

Sei Γ eine endliche Beschränkungssprache über dem Booleschen Bereich. Das Problem CSP(C) ist in Polynomialzeit entscheidbar, wenn Γ eine der folgenden sechs Operationen als Polymorphismus hat: die konstante unäre Operation 0; die konstante unäre Operation 1; die binäre UND-Verknüpfung ∧; die binäre ODER-Verknüpfung ∨; die ternäre Mehrheitsoperation {Anzeigestil Betreibername {Mehrheitlich} (x,j,z)=(xkeil y)Ve (xkeil z)Ve (Ywedge z);} die ternäre Minderheitsoperation {Anzeigestil Betreibername {Minderheit} (x,j,z)= xoplus yoplus z.} Andernfalls, das Problem CSP(C) ist NP-vollständig.

In dieser Formulierung, Es ist leicht zu überprüfen, ob eine der Lenkbarkeitsbedingungen erfüllt ist.

Properties of Polymorphisms Given a set Γ of relations, Es besteht eine überraschend enge Verbindung zwischen seinen Polymorphismen und der Rechenkomplexität von CSP(C).

Eine Relation R heißt primitiv positiv definierbar, oder kurz pp-definierbar, aus einer Menge Γ von Relationen, falls R(v1, ... , vk) ⇔ ∃x1 ... xm. C gilt für eine gewisse Konjunktion C von Beschränkungen aus Γ und Gleichungen über den Variablen {v1,...,vk, x1,...,xm}. Zum Beispiel, wenn Γ aus der ternären Relation nae besteht(x,j,z) halten, wenn x,j,z sind nicht alle gleich, und R(x,j,z) ist x∨y∨z, dann kann R durch R pp-definiert sein(x,j,z) ⇔ ∃a. naja(0,x,a) ∧ naja(j,z,¬a); Diese Reduktion wurde verwendet, um zu beweisen, dass NAE-3SAT NP-vollständig ist. Die Menge aller Relationen, die aus Γ pp-definierbar sind, bezeichnen wir mit ≪Γ≫. Wenn Γ' ⊆ ≪Γ≫ für einige endliche Restriktionsmengen Γ und Γ', dann CSP(C') reduziert sich auf CSP(C).[5] Gegeben sei eine Menge Γ von Relationen, Pol(C) bezeichnet die Menge der Polymorphismen von Γ. Umgekehrt, wenn O eine Menge von Operationen ist, dann Inv(Ö) bezeichnet die Menge der Relationen mit allen Operationen in O als Polymorphismus. Pol und Inv bauen zusammen eine Galois-Verbindung auf. Für jede endliche Menge Γ von Relationen über einem endlichen Bereich, ≪Γ≫ = Inv(Pol(C)) hält, das ist, die Menge der aus Γ pp-definierbaren Relationen kann aus den Polymorphismen von Γ abgeleitet werden.[6] Darüber hinaus, wenn Pol(C) ⊆ Pol(C') für zwei endliche Beziehungsmengen Γ und Γ', dann Γ' ⊆ ≪Γ≫ und CSP(C') reduziert sich auf CSP(C). Als Konsequenz, zwei Beziehungsmengen mit denselben Polymorphismen führen zu derselben Rechenkomplexität.[7] Generalizations The analysis was later fine-tuned: CSP(C) ist entweder in co-NLOGTIME lösbar, L-komplett, NL-komplett, ⊕L-vollständig, P-vollständig oder NP-vollständig und gegebenes Γ, man kann in polynomieller Zeit entscheiden, welcher dieser Fälle zutrifft.[8] Schaefers Dichotomie-Theorem wurde kürzlich auf eine größere Klasse von Relationen verallgemeinert.[9] Related work If the problem is to count the number of solutions, was durch #CSP gekennzeichnet ist(C), dann gilt ein ähnliches Ergebnis von Creignou und Hermann.[10] Sei Γ eine endliche Beschränkungssprache über dem Booleschen Bereich. Das Problem #CSP(C) ist in polynomieller Zeit berechenbar, wenn Γ eine Mal'tsev-Operation als Polymorphismus hat. Andernfalls, das Problem #CSP(C) ist #P-vollständig. Eine Mal'tsev-Operation m ist eine ternäre Operation, die erfüllt {Anzeigestil m(x,j,j)=m(j,j,x)=x.} Ein Beispiel für eine Mal'tsev-Operation ist die Minority-Operation in der Moderne, algebraische Formulierung des obigen Dichotomiesatzes von Schaefer. Daher, wenn Γ die Minoritätsoperation als Polymorphismus hat, es ist nicht nur möglich, CSP zu entscheiden(C) in polynomieller Zeit, aber um #CSP zu berechnen(C) in polynomieller Zeit. Es gibt insgesamt 4 Mal'tsev-Operationen auf booleschen Variablen, bestimmt durch die Werte von {Anzeigestil m(T,F,T)} und {Anzeigestil m(F,T,F)} . Ein Beispiel für weniger symmetrische ist gegeben durch {Anzeigestil m(x,j,z)=(xkeil z)Ve (neg. Keil (xvee z))} . Auf anderen Domänen, wie Gruppen, Beispiele für Mal'tsev-Operationen sind {Anzeigestil x-y+z} und {Anzeigestil xy^{-1}z.} Für größere Domains, selbst für eine Domain der Größe drei, die Existenz eines Mal'tsev-Polymorphismus für Γ ist keine hinreichende Bedingung für die Handhabbarkeit von #CSP mehr(C). Jedoch, das Fehlen eines Mal'tsev-Polymorphismus für Γ impliziert immer noch die #P-Härte von #CSP(C).

Siehe auch Max/Min CSP/Ones-Klassifikationstheoreme, ein ähnlicher Satz von Einschränkungen für Optimierungsprobleme Referenzen ^ Schaefer, Thomas J. (1978). "Die Komplexität von Erfüllbarkeitsproblemen". LAGER 1978. pp. 216–226. doi:10.1145/800133.804350. ^ Schäfer (1978, S.218 links) definiert eine affine Formel von der Form x1 ⊕ ... ⊕ xn = c, wobei jedes xi eine Variable ist, c ist eine Konstante, d.h. richtig oder falsch, und "⊕" bezeichnet XOR, d.h. Addition in einem booleschen Ring. ^ Chen, Hubi (Dezember 2009). "Ein Rendezvous der Logik, Komplexität, und Algebra". ACM Computing-Umfragen. 42 (1): 1–32. arXiv:cs/0611018. doi:10.1145/1592451.1592453. ^ Chen, Hubi (Dezember 2006). "Ein Rendezvous der Logik, Komplexität, und Algebra". SIGACT-Neuigkeiten (Logikspalte). arXiv:cs/0611018. ^ Chen (2006), S.8, Vorschlag 3.9; Chen verwendet eine Viel-Eins-Reduktion in Polynomzeit ^ Chen (2006), S.9, Satz 3.13 ^ Chen (2006), S.11, Satz 3.15 ^ Allender, Erich; Bauland, Michael; Immermann, Neil; Schnoor, Hennig; Vollmer, Heribert (Juni 2009). "Die Komplexität von Erfüllbarkeitsproblemen: Verfeinerung des Satzes von Schaefer" (Pdf). Zeitschrift für Computer- und Systemwissenschaften. 75 (4): 245–254. doi:10.1016/j.jcss.2008.11.001. Abgerufen 2013-09-19. ^ Bodirsky, Manuel; Pfingsten, Michael (2015). "Satz von Schaefer für Graphen". J. ACM. 62 (3): 19:1–19:52. arXiv:1011.2894. doi:10.1145/2764899. ^ Creignou, Nadia; Hermann, Michi (1996). "Komplexität verallgemeinerter Erfüllbarkeitszählprobleme". Information und Berechnung. 125 (1): 1–12. doi:10.1006/inco.1996.0016. ISSN 0890-5401. Kategorien: Constraint ProgrammingTheoreme in Computational Complexity Theory