Ich weiß aus dem Schäfer-Dichotomie-Theorem, dass nur wenige Arten von Erfüllbarkeitsproblemen in P vorliegen und jedes andere Problem NP-vollständig ist. Alle Algorithmen, die ich für sie kenne, verwenden jedoch spezifische Techniken, die für diese Art von Problem einzigartig sind, z. B. die Ausbreitung von Einheiten für Hornsat, lineare algebraische Techniken mod 2 für XORSAT und verschiedene andere Techniken für 2-sat. Gibt es einen allgemeinen Polytime-Algorithmus, der für alle diese Probleme in P funktioniert? Vielen Dank.
7
Antworten:
Schäfers Dichotomiesatz wird bewiesen, indem CSPs in zwei Typen unterteilt werden: diejenigen, die auf eines der wenigen spezifischen Probleme in P reduziert werden können, und das andere, auf das SAT reduziert werden kann (und somit NP-vollständig sind). Insbesondere ist jeder CSP des ersteren Typs entweder trivial (immer erfüllt durch die Zuweisung der Konstanten 0 oder der Konstanten 1), kann auf 2SAT reduziert werden, kann auf HORN-SAT reduziert werden oder kann auf XOR-SAT reduziert werden. Dies sind die einzigen Algorithmen, die Sie zur Lösung dieser CSPs benötigen. Es gibt keinen einzigen Algorithmus - es gibt eine endliche Liste von Algorithmen.
quelle
Suchen Sie nach Artikeln / Büchern von Vijay Chandru, John Hooker und John Franco. Einige ihrer Techniken verwenden die Ganzzahlprogrammierung (Betrachtung spezieller Strukturen in der Matrix, die durch die CNF-Klauseln der SAT-Instanz generiert werden). Die "Extended Horn" -Formeln haben eine spezielle Struktur, wenn sie als Graphen dargestellt werden, die sie polynomiell lösbar machen.
Um Franco aus seiner Umfrage von 2009 zu zitieren: Der Leser könnte den Eindruck haben, dass die Anzahl der polynomialzeitlösbaren Klassen aufgrund des berühmten Dichotomiesatzes von Schäfer recht gering ist. Dies ist jedoch nicht der Fall. Schäfer schlug ein Schema zur Definition von Klassen von Satzausdrücken mit einem verallgemeinerten Begriff von „Klausel“ vor. Er bewies, dass jede innerhalb seines Schemas definierbare Klasse entweder NP-vollständig oder polynomial lösbar war, und gab Kriterien an, um zu bestimmen, welche. Es können jedoch nicht alle Klassen innerhalb seines Schemas definiert werden. Die Horn- und XOR-Klassen können es sein, aber wir werden einige andere beschreiben, einschließlich Q-Horn, Extended Horn, CC-Balanced und SLUR, die nicht so definiert werden können. Der Grund dafür ist, dass Schaefers Schema auf Klassen beschränkt ist, die im Protokollbereich erkannt werden können .
quelle