Warum werden TSP-Löser benötigt, wenn es SAT-Löser gibt?

7

Concorde TSP ist ein Löser für TSP. SAT-Löser sind Löser für die boolesche Erfüllbarkeit. TSP und SAT sind NP-vollständig.

Warum also die Zeit damit verbringen, Concorde TSP zu entwickeln, wenn es damals eine Fülle von SAT-Lösern auf dem Markt gibt?

Jessica Cage
quelle

Antworten:

11

TL; DR : Polynomreduktion erhöht die Größe eines Problems; Mit einem bestimmten Löser können Sie die Struktur eines Problems ausnutzen .

Wenn Sie ein NP-vollständiges Problem auf ein anderes reduzieren, wächst die Größe des Problems normalerweise polynomiell. Zum Beispiel, wenn Sie einen HAMPATH in einem Diagramm mit reduzierenn Knoten zu SAT hat die resultierende Formel die Größe von Θ(n3)(Ich erinnere mich nicht an die Konstante, die bei einer einfachen TSP-> SAT-Reduktion auftritt). Wenn Sie das Cook-Levin-Theorem verwenden, ist das Wachstum möglicherweise sogar noch größer, da eine Turing-Maschine möglicherweise einen sehr großen (polynomyalen) Overhead hat. NP-Vollständigkeit ist meist eine theoretische Idee. Dies gilt auch für eine Reduzierung der Polynomzeit. Viele theoretische Arbeiten geben nur an, dass es eine Reduzierung gibt, und sagen nichts darüber aus, wie praktisch es ist.

Nehmen wir informell an, dass TSP so hart wie SAT ist. Dies bedeutet, dass ähnliche Rechenressourcen erforderlich sind, um TSP zu lösenn Knoten und SAT mit nKlauseln, wenn Sie für jedes Problem Solver auf dem neuesten Stand der Technik verwenden. Jetzt ist leicht zu erkennen, dass das Schreiben eines separaten Lösers praktischer ist, als das Problem auf SAT zu reduzieren und einen vorhandenen SAT-Löser zu verwenden. Es geht um Polynom-Overhead.

Es gibt noch etwas zu beachten: Genaue Probleme sind normalerweise einfacher als allgemeine. Wenn Sie TSP auf SAT reduzieren, weiß der SAT-Solver nichts über die zugrunde liegende Struktur der Formel. Und spezielle Löser für TSP befassen sich natürlich mit der Tatsache, dass die Eingabe ein Graph ist. Das Problem besteht darin, einen kürzesten Hamilton-Pfad zu finden, und so weiter.

Obwohl für einige Probleme eine Reduzierung auf SAT sinnvoll sein kann, meistens, wenn das Problem nicht gut untersucht ist (und keine coolen Löser existieren) und wenn die Reduzierung die Problemgröße nicht stark erhöht. SAT-Löser sind für viele praktische Zwecke immer noch sehr stark.

Ivan Smirnov
quelle
1
Ich denke, das ist im Wesentlichen die richtige Antwort. Es ist jedoch möglich, dass es eine Reduzierung von einem Problem auf ein anderes gibt, die die Größe nur ein wenig erhöht. SAT-Löser können auch intelligent sein und Strukturen erkennen, insbesondere wenn die Codierung des Problems geeignet ist. Daher ist es wahrscheinlich ein wenig Arbeit erforderlich, einen problemspezifischen Löser zu erstellen, der einen SAT-Löser übertrifft.
Juho