SAT-Löser mit speziellen Algorithmen wettbewerbsfähig machen

11

Was sind Hindernisse, um SAT-Löser mit speziellen Graph-Algorithmen wettbewerbsfähig zu machen? Mit anderen Worten, ist es möglich, SAT-Löser zu erwarten, die die Rolle des Algorithmus-Designers ersetzen können - dh in der Lage sind, die Problemstruktur automatisch zu erkennen und sie dann so schnell wie ein spezialisierter Algorithmus zu lösen?

Hier einige Beispiele, die meiner Meinung nach für die heutigen SAT-Löser eine Herausforderung darstellen:

  • Zählen unabhängiger Mengen der Größe . Die Codierung "x ist eine unabhängige Menge der Größe k" ergibt eine große Formel, die schwer zu lösen ist. Ein idealer SAT-Löser würde erkennen, dass dieses Problem bei einem Diagramm mit begrenzter Baumbreite leicht ist, wenn eine zusätzliche Variable "count" für Taschen hinzugefügt wird.k

  • Minimum Steiner Baum finden. Auch hier hat "Steiner-Baum" eine globale Einschränkung. Ein spezieller Algorithmus (wie hier ) erleichtert die Aufgabe jedoch durch Hinzufügen einer zusätzlichen Variablen

  • Jedes Problem, das sich auf planare perfekte Übereinstimmungen reduziert.

Jaroslaw Bulatow
quelle
passiert das nicht schon? Es ist ein beliebter Trick, ein Problem auf SAT zu reduzieren und dann einen Solver auszuführen.
Suresh Venkat
Ja, aber sind sie wettbewerbsfähig? Ich frage mich, ob es einen SAT-Löser gibt, der eine einfache Reihe von Einschränkungen akzeptiert, die den Eulerschen Teilgraphen eines planaren Graphen beschreiben, und #SAT in Polynomzeit ausführt
Jaroslaw Bulatow,

Antworten:

7

Es gibt ein schönes Papier, das hilft, die interne Struktur von SAT-Instanzen zu visualisieren. Siehe Visualisierung von SAT-Instanzen und -Läufen des DPLL-Algorithmus von Carsten Sienz (Erschienen in SAT 2004). Grundsätzlich wird ein Diagramm gezeichnet, das der Autor (nach einigen Regeln) als "variables Interaktionsdiagramm" bezeichnet, um die Beziehung zwischen den erfüllten Klauseln zu visualisieren. Der Autor zeigt dies durch mehrere Teilläufe von DPLL.

Der Hauptanspruch besteht darin, dass diese Visualisierungstechniken verwendet werden könnten, um die Struktur zu erkennen und einen geeigneten Algorithmus dafür zu entwerfen. Es ist jedoch immer noch nicht klar, wie wir Strukturen wie die im Papier vorgestellte effizient erkennen können. Es ist bekannt, dass sich SAT-Algorithmen für ein bestimmtes Problem bei anderen Problemen schlecht verhalten. Es gibt also "kein kostenloses Mittagessen", obwohl diese Behauptung meines Wissens nicht formell dargelegt werden kann.

Marcos Villagra
quelle
Ich denke, der relevante Satz "kein freies Mittagessen" ist das "kein freies Mittagessen für die Suche" no-free-lunch.org . Grundsätzlich können wir uns die Suche nach allen möglichen Problemstrukturen nicht leisten und müssen unsere Suche auf bestimmte Strukturen ausrichten. Ich denke, das ist in Ordnung, da menschliche Algorithmus-Designer das bereits tun
Jaroslaw Bulatow