Beste obere Schranken am SAT

43

In einem anderen Thread fragte Joe Fitzsimons nach "den derzeit besten Untergrenzen für 3SAT".

Ich mag den anderen Weg gehen: Was ist die besten aktuellen oberen Schranken für 3SAT? Mit anderen Worten, was ist die zeitliche Komplexität des effizientesten SAT-Lösers?

Ist es insbesondere denkbar, einen subexponentiellen (aber superpolynomiellen) Algorithmus für SAT zu finden?

cc.complexity-theory ds.algorithms sat upper-bounds MS Dousti
quelle

2

Ich weiß nichts über analytische Ergebnisse, aber Sie finden experimentelle Ergebnisse hier baldur.iti.uka.de/sat-race-2010/results.html (siehe die "HTML"

-Link

1

Dieser Fragentitel ist aufgrund der Existenz dieser Frage etwas irreführend: cstheory.stackexchange.com/questions/1295/sat-solver-download . Ich denke, Sie könnten es als "Beste Obergrenze für SAT" umformulieren?

Suresh Venkat

@Suresh: Die Frage, auf die Sie sich beziehen, bezieht sich auf "#SAT", während diese Frage SAT entspricht. Außerdem wurde diese Frage ungefähr eine Woche nach dieser gestellt. Wie auch immer, schlagen Sie immer noch vor, den Titel dieser zu ändern?

MS Dousti

Ja, denn ein "SAT Solver" ist ein bekanntes Objekt - eine eigentliche Codebasis zum Lösen von SAT. Google wird verwirrt sein und Leute, die hier nach Code suchen, weiterleiten :).

Suresh Venkat,

4

In Bezug auf die Motivation für diese Frage dachte ich, dass mehrere Personen SAT-Löser auf den 17x17-Instanzen ausprobiert hatten. Es scheint die Grenze dessen zu sein, was mit einem SAT-Löser gehandhabt werden kann. Sie könnten stattdessen einen parallelen Löser ausprobieren, aber ich hatte aufgrund der Beiträge von Bill Gasarch den Eindruck, dass Sie einen großen Aufwand benötigen würden. Sie können auch einen SMT-Solver mit einer geeigneten Theorie anwenden oder einen Constraint-Solver verwenden, der eine globale Constraint mit einem effizienten Propagator implementiert. In jedem dieser Fälle wäre die neue Idee, eine wichtige Eigenschaft auszudrücken, die mit Klauseln nur schwer zu realisieren ist.

András Salamon

38

Es gibt zwei Arten von "besten" SAT-Lösern, einen für die Theorie und einen für die Praxis.

Theorie

Kazuo Iwama, Kazuhisa Seto, Tadashi Takai, Suguru Tamaki, " Verbesserte randomisierte Algorithmen für 3-SAT ", ISAAC 2010.

randomisiertes für 3SAT. $O(1.32113^n)$

Timon Hertli, Robin A. Moser, Dominik Scheder, " Verbesserung der PPSZ für 3-SAT mithilfe kritischer Variablen ", 2011.

randomisiertes für 3SAT. $O(1.321^n)$

Konstantin Kutzkov, Dominik Scheder, " Mit CSP deterministisches 3-SAT verbessern ", 2010.

deterministisches für 3SAT. $O(1.439^n)$

Trainieren

Überprüfen Sie die SAT-Konferenz auf Wettbewerbsergebnisse für jedes Jahr.

Tian Liu
quelle

O ({1.32113}^{n})

$O(1.32113^n)$

@ Sadeq: Ich denke schon, aber nur für 3-SAT, nicht SAT.

Tian Liu

2

O ({1.321}^{n})

$O(1.321^n)$

10

{1.308}^{n}

$1.308^n$

21

Mir sind keine randomisierten Null-Fehler-Algorithmen (oder übrigens CoNE / Eadvice- Algorithmen
) für SAT bekannt, die bessere Grenzen haben als bekannte deterministische Algorithmen,
unabhängig davon, ob zugesagt wird, dass es höchstens eine zufriedenstellende Zuordnung gibt oder nicht.

Derandomizing HSSW Algorithmus für 3-SAT zeigt das

$\overset{\sim}{O}(1.3303^n)$

Die Derandomisierung von PPSZ für Unique-k-SAT zeigt, dass:

$n$
$O\hspace{.02 in}(1.3071^n)$ $O\hspace{.02 in}(1.4699^n)$

3-SAT schneller und einfacher - Einzigartige SAT-Grenzen für PPSZ Hold im Allgemeinen zeigen, dass (ursprünglich in Ryans Kommentar erwähnt )

"Es gibt einen randomisierten Algorithmus für 3-SAT mit
einseitigem Fehler, der in der Zeit abläuft $O\hspace{.02 in}(1.30704^n)$

"Es gibt einen randomisierten Algorithmus für 4-SAT mit
einseitigem Fehler, der in der Zeit abläuft $O\hspace{.02 in}(1.46899^n)$

Das Durchbrechen der PPSZ-Barriere für Unique 3-SAT führt
zu einem Ergebnis, das sich wie folgt zusammenfassen lässt:

"Es gibt einen randomisierten Algorithmus für Unique-3-SAT, der z $\: \epsilon = 1\hspace{-0.03 in}\big/\hspace{-0.06 in}\left(\hspace{-0.03 in}10^{\hspace{.02 in}24}\hspace{-0.04 in}\right) \:$
$S$
$\: O\hspace{-0.04 in}\left(2^{(S+o(1))\cdot n}\right) \:$ , $\;$ Der Algorithmus des aktuellen Papiers wird rechtzeitig ausgeführt $\: O\hspace{-0.04 in}\left(2^{(S-\epsilon+o(1))\cdot n}\right)$

Gemeinschaft
quelle

16

$O(a^n)$ $a = 2(k-1)/k$ $O(1.33334^n)$ $O(1.5^n)$

$O((a+\epsilon)^n)$ $a$ $\epsilon>0$

$O^*$

Robin Kothari
quelle

1

Warum sagst du "fast vollständig"? Habe ich etwas in der Zeitung verpasst?

András Salamon

1

O ((2 - \frac{2}{k + 1})^{n})

$O((2 - \frac{2}{k + 1})^n)$

k = 3

$k = 3$

O ({1.5}^{n})

$O(1.5^n)$

4

Ich sagte "fast vollständig", um anzuzeigen, dass es dort einen Epsilon-Faktor gibt. Ich vermute, man würde erwarten, dass eine vollständige Derandomisierung die gleiche Laufzeit erreicht (bis zu Polynomfaktoren). Oder vielleicht ist das unvernünftig zu erwarten.

Robin Kothari

1

@Grigory Yaroslavtsev: Ist der deterministische Moser-Scheder-Algorithmus für kSAT, den ich erwähnt habe, nicht schneller als der, den Sie zitiert haben? Vermisse ich etwas?

Robin Kothari

1

ϵ

$\epsilon$

12

Wie bereits erwähnt, handelt es sich bei dieser Frage um ein Duplikat, wenn Sie an theoretischen Laufzeitgarantien interessiert sind.

Aber ich möchte darauf hinweisen, dass, wenn Sie ein konkretes Problem (wie das von Ihnen erwähnte Farbproblem) wirklich lösen wollen, es meines Erachtens überhaupt keinen Sinn macht, theoretische Obergrenzen zu studieren.

Obwohl Sie "technische" Aspekte vermeiden wollten, würde ich vorschlagen, dass Sie einfach einige beliebte SAT-Löser nehmen, sie ausprobieren und sehen, was passiert (die meisten können dasselbe DIMACS-Dateiformat lesen, daher ist es einfach, es zu versuchen verschiedene Löser). Sie können sowohl positive als auch negative Überraschungen erleben. Kürzlich hatte ich eine Familie von SAT-Instanzen; Eine Reihe von Instanzen mit Zehntausenden von Variablen und mehr als einer Million Klauseln erwies sich als einfach zu lösen, während scheinbar viel einfachere Instanzen mit nur Hunderten von Variablen und Tausenden von Klauseln für jeden Löser, den ich ausprobierte, viel zu schwierig waren.

Jukka Suomela
quelle

8

Zusätzlich zu Jukkas Zusammenfassung gibt es zwei Hauptarten von SAT-Lösern: solche, die auf Umfrageweitergabe basieren und für zufällige SAT-Instanzen gut funktionieren, und solche, die Klausellernen in Kombination mit Einheitenauflösung verwenden und dazu neigen, zu funktionieren gut kombinatorische Struktur zu entdecken. Diese haben ein ganz anderes Verhalten. Die schlimmsten Fälle für SAT-Löser sind Fälle, die nicht befriedigend sind, bei denen jedoch der Raum von Nogoods eine komplexe Struktur aufweist, die nicht viel Beschneiden zulässt. Leider sind Instanzen aus der Kombinatorik in der Regel von dieser Art.

András Salamon

11

Timon Hertli, " 3-SAT Schneller und Einfacher - Einzigartige SAT-Grenzen für PPSZ Hold im Allgemeinen ", FOCS 2011.

$O(1.308^n)$

Kaveh
quelle

Ich gehe davon aus, dass jemand, der sich eine bessere Obergrenze einfallen lässt, dieses Papier zitiert. Es gab nur ein einziges Zitat zu dieser Veröffentlichung, nämlich "Ein Erfüllungsalgorithmus und eine Durchschnittsfallhärte für Formeln über die volle binäre Basis". Sie scheinen nur über bestimmte Arten von Formeln zu sprechen. Daher scheint dies die beste Obergrenze zu sein, die es bisher gab.

Tayfun Pay

@TayfunPay:

$\:$ Das unterste Papier in meiner Antwort zitiert dieses Papier.

$\;\;\;\;$

@ RickyDemer Uhuh! Ist es eine bessere Bindung als diese? Notation ist mir nicht so klar.

Tayfun Pay

@TayfunPay:

$\:$ Ja, und Sie können durch die beiden Papiere jagen, wie im Folgenden beschrieben.

$\:$

S_{3}

$S_3$

S_{k}

$S_k$

$\:$ Oben auf Seite 11 steht, dass ihr Algorithmus die gleiche Grenze wie PPSZ hat, was bedeutet, dass sie nicht mehr als das zeigten, was ich in meinem vorherigen Satz erwähnt habe.

$\:$ (Fortsetzung ...)

$\hspace{.35 in}$

(... Fortsetzung)

$\:$

S

$S$

2^{S \cdot n}

$2^{S\cdot n}$

$\:$

S

$S$

S_{3}

$S_3$

$\;\;\;$

8

Es ist für 3SAT unmöglich, subexponentielle Algorithmen zu verwenden, es sei denn, die Exponentialzeithypothese ist falsch.

Kazuo Iwama, Suguru Tamaki, Verbesserte Obergrenzen für 3-SAT , 2004.

$O({1.324}^n)$

Daniel Rolf, Verbesserte Bindung für den PPSZ / Schoning-Algorithmus für 3-SAT , 2005.

$O({1.32216}^n)$

Mohammad Al-Turkistany
quelle

15

Ist das nicht eine Tautologie?

Tsuyoshi Ito

1

2^{o (n)}

$2^{o(n)}$

Die Arbeit von Kazuo Iwama et al. (2004) ist neuer als Schönings (1999). Ich frage mich, ob noch aktuellere Ergebnisse vorliegen.

MS Dousti

8

Um mögliche Verwechslungen zu vermeiden, bezieht sich mein letzter Kommentar auf den ersten Satz der Antwort: „Es ist für 3SAT unmöglich, subexponentielle Algorithmen zu haben, es sei denn, die Exponentialzeithypothese (ETH) ist falsch.“ Mein Verständnis ist, dass die Exponentialzeit ist Die Hypothese ist die Hypothese, die besagt, dass es für 3SAT keinen Algorithmus gibt, dessen Laufzeit in Bezug auf die Anzahl der Variablen subexponentiell ist (dh 2 ^ {o (n)}).

Tsuyoshi Ito

10

Und um weitere Verwirrung zu vermeiden, möchte ich hinzufügen, dass Tsuyoshi, als er seinen Kommentar veröffentlichte, in der Antwort nur diesen einen Satz enthielt, was seinen Kommentar sehr zutreffend machte.

Robin Kothari

7

Dieser Beitrag befasst sich mit Obergrenzen für SAT. Diese eine beschäftigt sich mit besten unteren Grenzen. Dieser Link enthält Einzelheiten zum jährlichen Wettbewerb zum Vergleich von SAT-Solver-Implementierungen, die alle heruntergeladen werden können. Der Einfachheit halber könnten Sie mit SAT4J beginnen , einer Java-basierten Bibliothek für SAT-Lösungen.

Dave Clarke
quelle

Stellt sich heraus , diese Frage wurde bereits gefragt , bevor; Ich habe es beim Durchsuchen der Website einfach nicht gesehen. Tian Lius Antwort auf die Frage der oberen Schranken ist genau das, wonach ich gesucht habe. Danke für die Links, Dave!

Daniel Apon

1

Dies ist ein Beweis dafür, dass ich zu viel Zeit hier verbringe ;-)

Dave Clarke

Wir sind froh, dass Sie :)

Suresh Venkat

2

Ich bin mir nicht sicher, ob ich sat4J empfehlen würde, es ist nicht nur deutlich langsamer als auf dem neuesten Stand der Technik, sondern auch etwas komplexer. Es ist jedoch richtig, dass es aufgrund der objektorientierten Struktur gut anpassbar ist. MiniSat ist sehr gut geschrieben und 2.2 ist auf dem neuesten Stand der Technik.

Mikolas

3

Der beste deterministische Algorithmus für 3-SAT hat jetzt die Obergrenze 1.32793 ^ n, siehe https://arxiv.org/abs/1804.07901 von Sixue Liu. Grundsätzlich wurden in diesem Artikel die Obergrenzen für alle k-SAT verbessert.

ON KI Wong
quelle

Beste obere Schranken am SAT

Antworten:

Theorie

Trainieren