Unterscheidungsentscheidungsverfahren vs SMT-Löser vs Theorembeweiser vs Beschränkungslöser

Diese Begriffe verwirren mich. Wie ich es verstehe

• SAT-Löser: Bestimmen Sie die Erfüllbarkeit der Aussagenlogik (mit DPLL oder lokaler Suche).
• Entscheidungsverfahren ist ein Verfahren, um die Erfüllbarkeit einer bestimmten entscheidbaren Theorie erster Ordnung zu bestimmen.
• SMT-Solver ist ein SAT-Solver + Entscheidungsverfahren.
• Theorembeweiser bezeichnet so etwas wie dynamische Logik, zB das KeY-Tool
• Constraint Solver: Ich weiß es nicht.

Aber ich sehe Leute, die Z3 als Theorembeweiser bezeichnen. Ich weiß also nicht, wie ich diese Begriffe unterscheiden soll. Und was ist der allgemeinste Begriff für alle von ihnen? Vielen Dank.

SMT-Solver ist ein SAT-Solver + Entscheidungsverfahren

Ein SAT-Löser ist ein Löser für ein Entscheidungsproblem: Das SAT-Problem ist ein Entscheidungsproblem. Zusätzlich ist dieses Entscheidungsproblem "selbstreduzierbar":

Das SAT-Problem ist selbstreduzierbar, dh jeder Algorithmus, der korrekt antwortet, wenn eine SAT-Instanz lösbar ist, kann verwendet werden, um eine zufriedenstellende Zuordnung zu finden

- ( Wikipedia )

Dies bedeutet, dass SAT-Löser zusätzlich zur Problementscheidung auch die zufriedenstellende Aufgabe erteilen können.

TL; DR SMT-Löser lösen eine Verallgemeinerung des SAT-Problems in Abhängigkeit von den in der Theorie zulässigen Typen / Einschränkungen. Darüber hinaus ermöglichen sie auch das Codieren von Typbeziehungen höherer Ebenen als die SAT-Codierungen zulassen.

Ein SAT-Löser befasst sich normalerweise mit vielen einzelnen booleschen Variablen, die nur durch die Klauseln / Einschränkungen des CNF verknüpft sind . Ein QF_BV (quantifier-free bitvector) -Theorie-SMT-Löser ist im Grunde ein SAT-Löser + weitere Informationen zu den Beziehungen. Beispielsweise kann ein QF_BV-SMT-Löser auf SAT ¹ reduziert werden . Warum also einen QF_BF-SMT-Solver verwenden? Der Hauptvorteil besteht darin, dass in SAT eine Ganzzahl durch verschiedene Variablen dargestellt wird, die auf den ersten Blick als nicht verwandt erscheinen können. Ein SAT-Löser würde viel Zeit damit verbringen, einfache Beziehungen wie lernen.$(A = B) \wedge (B = C) \implies (A = C)$

1. Siehe Beaver SMT-Löser, der sogar das entsprechende SAT-Problem ausgeben kann, das gelöst werden müsste.

Obwohl der QF_BV-SMT-Solver diesen Vorteil gegenüber einem SAT-Solver hat, halte ich dies nicht für einen Komplexitätsvorteil: Beide sind im Wesentlichen gleichwertig und benötigen exponentielle Zeit, um ihre Worst-Case-Probleme zu lösen. In der Praxis ist ein QF_BV-SMT-Löser aufgrund dieser zusätzlichen Kenntnisse möglicherweise viel schneller. Siehe meine Antwort auf die Grenzwerte von SMT-Solvern , um ein Beispiel für etwas zu finden, das als "hart" eingestuft wird und an dem (aktuelle) QF_BV-SMT-Solver und SAT-Solver ersticken würden.

Es gibt auch SMT-Löser, die versuchen, noch schwierigere Probleme als die Boolesche Erfüllbarkeit zu lösen (z. B. Typen und Einschränkungen für Realwerte zulassen oder Quantifizierer zulassen). Offensichtlich sind diese theoretisch mindestens so langsam wie ein SAT-Löser. Diese SMT-Löser lösen eine Verallgemeinerung des SAT-Problems. Anstatt binäre Variablen zu verwenden, erlaubt jede "Theorie" Beziehungen / Einschränkungen über verschiedene Bereiche, wie zum Beispiel reelle oder quantifizierte (für alle) Einschränkungen.

Theorembeweiser

$P=NP$

Aber solche Änderungen könnten im Vergleich zur Revolution an Bedeutung verlieren, was eine effiziente Methode zur Lösung von NP-vollständigen Problemen in der Mathematik selbst verursachen würde. Laut Stephen Cook ^[19]

... es würde die Mathematik transformieren, indem es einem Computer ermöglicht wird, einen formalen Beweis für jeden Satz zu finden, der einen Beweis von angemessener Länge enthält, da formale Beweise in polynomieller Zeit leicht erkannt werden können. Beispielprobleme können durchaus alle CMI-Preisprobleme umfassen.

- ( Wikipedia )

[19]: Cook, Stephen (April 2000). Das P gegen NP Problem. Clay Mathematics Institute (PDF) .

$P=NP$

Im Moment verwenden automatisierte Theoreme meistens Heuristiken oder exponentielle Zeitalgorithmen (sind aber immer noch hilfreich).

Constraint-Löser

Dies sind normalerweise Umformulierungen der SAT / SMT-Löser in andere Sprachen. Wenn Sie jemals einen SAT / SMT-Löser zur Lösung eines Problems verwendet haben, können Sie die nicht deterministische Fähigkeit des Lösers wirklich lieben. Das heißt, anstatt dem Computer mitzuteilen, wie etwas zu tun ist, sagen Sie ihm, was Sie möchten , d. H. Welche Eigenschaften die Ausgabe haben soll und ein SAT / SMT-Löser wird sie nicht deterministisch ausfüllen, ohne Sie mit den Implementierungsdetails zu belasten. Diese Art von Programmierparadigma ist sehr ansprechend und wird als Einschränkungsprogrammierung bezeichnet. Um es auszuführen, muss ein Einschränkungslöser verwendet werden (der abhängig von den Typen und Einschränkungen, die Sie verwenden können, möglicherweise einen SAT / SMT-Löser im Backend verwendet). .

Aber ich sehe Leute, die Z3 als Theorembeweiser bezeichnen. Ich weiß also nicht, wie ich diese Begriffe unterscheiden soll.

AFAIK, Z3 ist eine Suite mit vielen Werkzeugen, darunter ein SMT-Löser, mehrere Theoremprüfungs- / Modellprüfungssprachen und vieles mehr.

Und was ist der allgemeinste Begriff für sie alle?

Ich denke, die Verallgemeinerung des Erfüllbarkeitsproblems ist Satisfiability Modulo Theories , und daher wäre "SMT Solver" der allgemeinste von allen. Allerdings lösen nicht alle tatsächlichen SMT-Solver-Implementierungen alle Theorien. Dies bedeutet also nicht, dass alle SMT-Solver gleich allgemein sind.