Bekannte Klassen von Booleschen Formeln, die Beweise mit exponentiell langer Auflösung erfordern

27

In SAT-Solvern finden Sie häufig Schnittebenenmethoden, variable Propagierung, Branch-and-Bound, Klausellernen, intelligentes Backtracking oder sogar handgewebte menschliche Heuristiken. Doch seit Jahrzehnten verlassen sich die besten SAT-Löser stark auf Auflösungsprüftechniken und verwenden eine Kombination aus anderen Dingen, um die Suche zu erleichtern und den Auflösungsstil zu steuern. Offensichtlich wird vermutet, dass JEDER Algorithmus zumindest in einigen Fällen die Erfüllbarkeitsfrage in der Polynomzeit nicht entscheidet.

1985 bewies Haken in seinem Aufsatz "The intractability of resolution", dass das in CNF kodierte Pigeon Hole-Prinzip keine polynomgroßen Auflösungsnachweise zulässt. Dies beweist zwar, dass auflösungsbasierte Algorithmen schwer zu handhaben sind, gibt jedoch auch Kriterien an, anhand derer innovative Löser beurteilt werden können. Tatsächlich ist eine der vielen Überlegungen, die heute bei der Entwicklung eines SAT-Lösers angestellt werden müssen, die voraussichtliche Leistung auf bekannten "harten" Fällen.

Eine Liste von Klassen von Booleschen Formeln zu haben, die nachweislich Auflösungsnachweise in exponentieller Größe zulassen, ist in dem Sinne nützlich, als es "schwierige" Formeln gibt, mit denen neue SAT-Löser getestet werden können. Welche Arbeit wurde geleistet, um solche Klassen zusammenzustellen? Hat jemand eine Referenz, die eine solche Liste und ihre relevanten Beweise enthält? Bitte geben Sie pro Antwort eine Klasse von Booleschen Formeln an.

Ross Snider
quelle
Community-Wiki?
Opt
Ich habe dieses Community-Wiki gemäß dem Vorschlag erstellt.
Ross Snider
1
Ein zusätzlicher Aspekt zu dieser Frage, der mich interessiert: Gibt es explizit bekannte Poly-Size-Proofs für eine erweiterte Auflösung für diese harten Fälle (wie Cooks Beweis für schwache Formeln für Taubenlöcher)?
MGwynne

Antworten:

21

Hard Instances zur Lösung :

  1. Tseitins Formeln (über Expandergraphen).

  2. Schwaches ( bis ) Pigeonhole-Prinzip (Exponential in unteren Grenzen, für jedes ).n n m > nmnnm>n

  3. Zufällige 3CNFs mit Variablen und -Klauseln für .O ( n 1,5 - ε ) 0 < ε < 1 / 2nO(n1.5ϵ)0<ϵ<1/2

Gute, relativ aktuelle technische Übersicht über die unteren Grenzen der Beweiskomplexität, siehe:

Nathan Segerlind: Die Komplexität von Aussagenbeweisen. Bulletin of Symbolic Logic 13 (4): 417-481 (2007), verfügbar unter: http://www.math.ucla.edu/~asl/bsl/1304/1304-001.ps

Iddo Tzameret
quelle
Dies ist ein gutes Beispiel für eine Antwort. Es wäre eine noch bessere Antwort, wenn es in mehrere aufgeteilt wäre.
Ross Snider
9

Es gibt eine Reihe guter Umfragen und Bücher zur Komplexität von Aussagenbeweisen, die solche Listen enthalten. Viele Beweissysteme simulieren die Auflösung, daher ist jede Formel, die für sie schwierig ist, schwierig für die Auflösung.

Bücher:
1. Jan Krajicek, "Bounded Arithmetic, Propositional Logic und Complexity Theory", 1995
2. Stephen A. Cook und Phoung The Neguyen, "Logical Foundations of Proof Complexity", 2010

Umfragen:
1. Paul Beame und Toniann Pitassi, "Propositionelle Beweiskomplexität: Vergangenheit, Gegenwart und Zukunft", 2001
2. Samuel R. Buss, "Gebundene arithmetische und propositionelle Beweiskomplexität ", 1997
3. Alasdair Urquhart, "Die Komplexität von aussagekräftige Beweise ", 1995

Siehe auch die hier und hier aufgeführten .

Kaveh
quelle
8

Ein weiteres hartes Beispiel für die Lösung sind die verstümmelten Schachbrettformeln. Sie besagen, dass ein Schachbrett mit zwei diagonal gegenüberliegenden fehlenden Ecken nicht mit Plättchen bedeckt werden kann. Sehen:2 × 12n×2n2×1

Michael Alekhnovich. Verstümmeltes Schachbrettproblem ist exponentiell schwer zu lösen. Theoretical Compututer Science 310 (1-3): 513 & ndash; 525 (2004). http://dx.doi.org/10.1016/S0304-3975(03)00395-5

Jan Johannsen
quelle
8

Pavel Pudlák hat kürzlich eine exponentielle Untergrenze für Resolutions-Widerlegungen der Formeln gezeigt, die aus dem Ramsey-Theorem für . Diese Formeln haben Klauseln und für jede Teilmenge der Größe , sie sind aufgrund des Ramsey-Theorems nicht befriedigend. Diese Untergrenze war ein seit langem offenes Problem, der Beweis wird in diesem ECCC-Bericht veröffentlicht . k = 1n(k)22i,jKxi,ji,jK¬xi,jK{1,...,n}| K| =kk=12logni,jKxi,ji,jK¬xi,jK{1,,n}|K|=k

Jan Johannsen
quelle
Vielen Dank. Dies ist eine sehr interessante Antwort (obwohl die Notation etwas anders ist, könnte ich folgen). Mein Studienberater hat Ramsey Theory ausgiebig studiert. Es gelang ihm, auch dieses Interesse an mir zu wecken.
Ross Snider
1

Unterhält DIMACS keine Beispielsätze von harten SAT-Instanzen? Ich konnte es dort nicht mit nur einem flüchtigen Blick finden, aber wenn Sie "SAT" in das Suchfeld eingeben, werden viele Treffer angezeigt, einschließlich mehrerer Artikel / Vorträge auf harten SAT-Instanzen.

Kurt
quelle
Besondere harte Instanzen (im Gegensatz zu Instanzfamilien ) sind hier satcompetition.org (Siehe "Benchmarks".)
Radu GRIGore