Übliche Methode zur Lösung von Erfüllbarkeitsproblemen, die in P liegen

7

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.

Ari
quelle
Die Frage ist eigentlich gar nicht so aussagekräftig, da es keinen technischen Weg gibt, "verschiedene Algorithmen" zu unterscheiden. Ein Algorithmus, der viele verschiedene Algorithmen als Unterprogramme aufruft, ist immer noch ein Algorithmus. Es gibt hier jedoch eine natürliche Vermutung, dass möglicherweise ein einheitlicherer Ansatz existiert.
VZN

Antworten:

7

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.

Yuval Filmus
quelle
Vielen Dank. Ist es nachweisbar, dass es keine anderen Algorithmen als diese endliche Liste gibt, oder ist das genau das, was wir annehmen?
Ari
Eine detailliertere Aussage des Schäfer-Theorems enthält dieses Ergebnis. In der Einstellung des Satzes ist es beweisbar, dass diese Liste alles ist, was erforderlich ist.
Yuval Filmus
Gegeben eine Formel fGibt es Algorithmen, um zu bestimmen, welche Kategorie ffällt in?
Hengxin
Der Algorithmus hängt nicht von der Formel ab, sondern von den zulässigen Prädikaten. Ich glaube, es ist möglich festzustellen, in welche Klasse ein CSP-Typ fällt, aber ich bin kein Experte in diesem Bereich.
Yuval Filmus
3

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 .

Martin Seymour
quelle
Ein verfeinertes Bild ist Allender et al. Zu verdanken : eccc.hpi-web.de/report/2004/100/download .
Yuval Filmus