Sind Schaltungen mit Quasi-Polynomgröße für 3-SAT trivial?

Angenommen, wir betrachten 3-SAT mit Variablen und Klauseln. Ich erforsche eine Methode, die anscheinend Zeit / Raum benötigt, um ein SAT-Problem zu lösen, das dieser Beschreibung entspricht, und zwar innerhalb eines Fehlers, der auf einen beliebigen Betrag eingestellt werden kann. Es gibt jedoch einen Haken. $v$ $c$ $O(v^{2+\log c})$

Dieses Verfahren erfordert einen Satz vorberechneter Werte, wonach ein beliebiges 3-SAT-Problem gelöst werden kann, das der obigen Beschreibung entspricht. Die vorberechneten Werte sind eine Menge der Größe wobei jeder Wert Platz einnimmt . Das eigentliche Problem besteht darin, dass die Berechnung jedes dieser Werte dauern kann . Es besteht die Möglichkeit, dass ich einen Weg finde, diese Berechnungen zu beschleunigen. $O(v^{2+\log c})$ $O(1)$ $O(2^v)$

Ich denke, dass die Grenzen selbst die in dieser Frage dargestellten oberen Grenzen überschreiten (für kleines ). Ich frage mich also, ob es einen trivialen Weg gibt, die von mir beschriebenen Obergrenzen zu erreichen, wenn wir -Vorberechnungen zulassen. $c$ $O(v^{2+\log c})$

Ich möchte diese Forschung fortsetzen und hoffentlich meine Ergebnisse veröffentlichen, wenn alles klappt, aber zuerst möchte ich wissen, ob es einen trivialen Weg gibt, dies auch oder besser zu tun.

AKTUALISIEREN

Ich habe verwandte Probleme untersucht und diesen Algorithmus untersucht. Ich habe diese Frage auf der IT-Sicherheitsseite von StackExchange in Bezug auf das Knacken von Passwörtern und SAT gestellt, wenn Sie interessiert sind. Mindestens eine der Antworten spiegelt dies wider.

ds.algorithms sat upper-bounds Matt Groff
quelle

Sie sagen, es dauert O (N ^ 2 + logc) Zeit / Raum ... Also ist es nicht in PSPACE? Aber in QSPACE (Quasi-Raum)?

Tayfun Pay

@Tayfun Pay: Es läuft in . Es ist ein deterministischer Algorithmus, der einem Ergebnis modulo eine Primzahl (beachten Sie, dass dieses Ergebnis für den Rest des Algorithmus ausreicht, um eine zufriedenstellende Zuordnung zu bestimmen). Es kann für jede Primzahl ausgeführt werden. Das Laufen für mehr als eine Primzahl erhöht die Chance, eine zufriedenstellende Aufgabe zu finden. Es besteht die Möglichkeit, eine zufriedenstellende Zuordnung von finden, falls eine existiert .

O (v^{(2 + \log c)})

$O(v^{(2+\log c)})$

p

$p$

(p - 1) / p

$(p-1)/p$

Matt Groff

Benötigt es O (N ^ (2 + log (c))) SPACE?

Tayfun Pay

@Tayfun Pay: Ja. Ich habe noch keinen Weg gefunden, die Platzüberlegungen zu reduzieren.

Matt Groff

Ich würde vorschlagen, den Titel in einen angemesseneren zu ändern. Der aktuelle Titel sieht nicht ansprechend aus, während die Frage selbst so aussieht.

Yoshio Okamoto

Antworten:

Wenn das, was Sie studieren, klappen würde, wäre es definitiv nicht trivial.

Dies würde bedeuten, dass 3SAT (ungleichmäßige) Schaltungen der Größe . Dann hätte jede Sprache in (und der Polynomzeithierarchie) quasi-polynomielle (dh ) Schaltungen. $n^{O(\log n)}$ $NP$ $n^{O(\log^c n)}$

Selbst wenn es Vorverarbeitungszeit dauerte , um eine Datenstruktur mit einer Größe von nur zu erzeugen, die dann beliebige 3SAT-Anfragen der Größe in randomisierte Zeit mit hoher Wahrscheinlichkeit, 3SAT hätte quasi-polynomiale Größenschaltungen, wobei die bekannte Übersetzung von randomisierten Algorithmen in Schaltungen verwendet würde. Dies würde die bekannten Algorithmus-Zeitgrenzen aufgrund der Vorverarbeitung nicht verbessern, wäre aber als ungleichmäßiges Ergebnis immer noch äußerst interessant. $2^{2^n}$ $2^{O(\log^2 n)}$ $n$ $2^{O(\log^2 n)}$

Was meinst du mit "innerhalb eines Fehlers, der auf einen beliebigen Betrag eingestellt werden kann"? Ist der Algorithmus randomisiert?

Ryan Williams
quelle

:Danke für deine Antwort. Der Algorithmus ist nicht randomisiert. Die tatsächliche Laufzeit des Algorithmus selbst ist nicht ganz so einfach, wie ich es beschrieben habe. Grundsätzlich können wir es jedoch durch wiederholte Läufe laufen lassen, um Fehler zu beseitigen. Wenn wir es also mal durchlaufen , würde sich die Fehlerwahrscheinlichkeit unter verringern . Ich zögere, die Details preiszugeben, weil ich mir Sorgen mache, dass sie zu viel über den Algorithmus verraten.

x

$x$

1 / (2^{x})

$1/(2^x)$

Matt Groff

Wie kann der Algorithmus nicht randomisiert werden, aber Sie können ihn wiederholt ausführen, um Fehler zu reduzieren? Ich denke, dass Sie wahrscheinlich noch ein paar Details angeben müssten, um Ihre Frage zu verstehen.

Ryan Williams

Sein Algorithmus ist so, dass (wenn es funktioniert) für jede Primzahl der Algorithmus eine zufriedenstellende Zuordnung findet , wenn die Anzahl der erfüllenden Zuweisungen kein Vielfaches von ist. Er bezieht sich (fälschlicherweise) darauf als "eine Änderung der Suche nach einer befriedigenden Zuordnung von , falls vorhanden ." Wenn die Abhängigkeit der Laufzeit von nicht sehr groß ist, ergibt dies (deterministische) quasi-polynomgroße Schaltungen für SAT.

p

$p$

p

$p$

$\;$

(p - 1) / p

$(p-1)/p$

$\hspace{0.9 in}$

p

$p$

$\;\;$

Der Vorverarbeitungsschritt benötigt . Kann ich einen Verweis auf "die bekannte Übersetzung von randomisierten Algorithmen in Schaltkreise" haben? Wenn Sie also Fehler reduzieren möchten, müssen Sie die Vorverarbeitung mal ausführen . Ich bezweifle, dass dies in eine Quasi-Schaltung übersetzt werden kann. Welchen Vorteil hat dies gegenüber einem trivialen Algorithmus?

p

$p$

n

$n$

Zirui Wang

@ZiruiWang: nachschlagen . Angenommen, die Datenstruktur beantwortet Anfragen korrekt mit einer Wahrscheinlichkeit von . Nehmen Sie Kopien der Datenstruktur der Größe jeweils mit unterschiedlichen Zeichenfolgen zufälliger Bits versehen sind. Nehmen Sie die Mehrheitsantwort aller Kopien. Dies ist ein quasipolynomialer zeitlich randomisierter Algorithmus mit einem Fehler von weniger als 1/2 . Dies kann durch Hardcodierung eines geeigneten Keims in eine Schaltung mit Quasipolynomgröße umgewandelt werden.

B P P \subset P / p o l y

$BPP \subset P/poly$

3 / 4

$3/4$

100 n

$100n$

2^{O (\log^{2} n)}

$2^{O(\log^2 n)}$

1 / 2^{n}

$1/2^n$

Ryan Williams

Ich weiß nicht, ob Ihr Ergebnis - falls gültig - ein nicht trivialer Fortschritt wäre, aber hier ist eine Art von Problem, an dem Sie es testen könnten:

Problem. Fixiere eine Funktion . Wenn , finde so, dass . $f:\{0,1\}^n \to \{0,1\}^n$ $y \in \{0,1\}^n$ $x \in \{0,1\}^n$ $f(x)=y$

Wenn effizient berechnet werden kann (z. B. durch eine kleine Schaltung), impliziert Ihr Ergebnis eine Lösung für dieses Problem. $f$

In der kryptografischen Welt führt der bekannteste Algorithmus für dieses Problem eine Vorberechnung (nur abhängig von ) durch, die Zeit und Raum erfordert und einige Ratschläge der Größe ausgibt. ;; dann, da , kann es finden in Zeit, mit der Beratung Zeichenfolge der Größe vom precomputation. Sie können den Kompromiss zwischen Raum und Zeit anpassen, um eine Hinweiszeichenfolge der Größe und die Zeit , solange $f$ $2^n$ $2^{2n/3}$ $2^{2n/3}$ $x$ $y$ $2^{2n/3}$ $2^{2n/3}$ $S$ $T$ $S \sqrt{T} = 2^n$ . Soweit ich weiß, wird diese Komplexität als die bestmögliche für Algorithmen angesehen, die keine der internen Strukturen von berücksichtigen . Insbesondere ist es wahrscheinlich optimal, wenn eine kryptografisch sichere Hash-Funktion ist. (Diese Technik ist als Hellman-Zeit-Raum-Kompromiss bekannt.) $f$ $f$

Wenn Ihre Technik also besser als der Hellman-Zeit-Raum-Kompromiss bei einem kryptografisch sicheren , wäre dies sicherlich eine Neuigkeit. $f$

DW
quelle