Beste aktuelle Raumuntergrenze für SAT?

Im Anschluss an eine vorherige Frage ,

was sind die besten aktuellen Raum untere Schranken für SAT?

Mit einer Leerzeichenuntergrenze meine ich hier die Anzahl der von einer Turing-Maschine verwendeten Arbeitsbandzellen, die ein binäres Arbeitsbandalphabet verwendet. Ein konstanter additiver Term ist unvermeidlich, da ein TM interne Zustände verwenden kann, um eine feste Anzahl von Arbeitsbandzellen zu simulieren. Ich bin jedoch daran interessiert, die häufig implizit belassene multiplikative Konstante zu steuern: Der übliche Aufbau erlaubt eine willkürliche Komprimierung von Konstanten über größere Alphabete, so dass die multiplikative Konstante dort nicht relevant ist, aber mit einem festen Alphabet sollte es möglich sein, dies zu berücksichtigen.

Zum Beispiel benötigt SAT mehr als $\log\log n + c$ Speicherplatz; andernfalls würde diese durch Simulation zu einer Zeitobergrenze von $n^{1+o(1)}$ , und dadurch würde die kombinierte Raum-Zeit-Untergrenze für SAT von $n^{1.801+o(1)}$ verletzt (siehe die Verknüpfung) Frage). Es scheint auch möglich zu sein, dieses Argument zu verbessern, um zu argumentieren, dass SAT mindestens $\delta\log n + c$ Platz für ein kleines positives $\delta$ , das $0.801/C$ , wobei $C$ der konstante Exponent bei der Simulation eines raumbegrenzten TM durch ein zeitbegrenztes TM ist.

Leider ist $C$ in der Regel recht groß (und in der üblichen Simulation, bei der die Bänder eines TM zunächst über ein größeres Alphabet auf einem einzigen Band codiert werden, mindestens 2). Solche Schranken mit $\delta \ll 1$ sind eher schwach, und ich wäre besonders an einer Raumuntergrenze von interessiert $\log n + c$ . Ein unbedingter Zeit gebunden unteren $\Omega(n^d)$ Schritte, für einige groß genug , um konstante $d > 1$ , würde bedeuten , einen solchen Raum niedriger durch Simulation gebunden. Zeituntergrenzen von $\Omega(n^d)$ für $d>1$ sind derzeit nicht bekannt, geschweige denn für große $d$ .

Anders ausgedrückt, ich suche nach etwas, das eine Folge der Untergrenzen der superlinearen Zeit für SAT ist, das aber möglicherweise direkter erhalten werden kann.

cc.complexity-theory sat lower-bounds space-bounded space-complexity András Salamon
quelle

Wie in dieser anderen Antwort (z. B. von RW) scheint die getrennte Fokussierung auf untere Zeit- oder Raumgrenzen unerreichbar zu sein und nur schwache / generische bekannte Grenzen zu haben, und die führende Forschung auf diesem Gebiet scheint ein relativ neueres Konzept hervorzubringen von kombinierter Zeit-Raum-Komplexität.

VZN

Antworten:

Es sieht so aus, als ob die bekannteste Bindung (für Multitape-Turing-Maschinen) logarithmisch ist.

Angenommen Bits binärer worktape genug ist , um zu entscheiden , ob ein -Bit - CNF Formel erfüllbar ist, für alle groß genug . Durch die Standard - Simulation, ein TM mit besagt , dass Verwendungen höchstens Bits von Raum kann durch ein TM simuliert werden, die höchstens hat $\delta\log n$ $n$ $n$ $q$ $s$ $qns2^s = 2^{s+\log n + \log s + \log q}$ verschiedene Konfigurationen. Wann immer die Maschine akzeptiert, gibt es eine Folge von (nicht deterministischen) Bewegungen, die einen Akzeptanzzustand erreichen, der höchstens so lang ist wie diese Anzahl von Konfigurationen. Wenn , beträgt dies höchstens (beachte, dass für alle Eingangslängen gleich bleibt ). Auf einem separaten Zählband ist $s = \Omega(\log n)$ $2^{s(2+o(1))}$ $q$ $n$ $M$ kann diese Menge zuerst unär schreiben, dann bei jedem Schritt der Simulation eines der Symbole des Zählers löschen und die Berechnung beenden, falls ihm jemals die Zählersymbole ausgehen. Dies erzeugt einen konstanten Overhead-Faktor (etwa 3), der vom Term im Exponenten absorbiert wird . Daher sind Schritte ausreichend. $o(1)$ $2^{s(2+o(1))}$

Unter der Annahme ist das Zeit-Raum-Produkt also höchstens . $s \le \delta\log n$ $\delta\log n2^{\delta\log n(2+o(1))} = n^{\delta(2+o(1))}$

Rahul Santhanam zeigte im Jahr 2001 (siehe doi: 10.1016 / S0020-0190 (00) 00227-1 ), dass das Raum-Zeit-Produkt für eine Turing-Maschine, die SAT entscheidet, mindestens ; sein Argument gilt auch für nichtdeterministische Maschinen. Daher werden und mindestens Bits des binären Arbeitsbands benötigt. $\Omega(n^{2-o(1)})$ $\delta \ge 1$ $\log n$

Im Allgemeinen ändern zusätzliche Arbeitsbänder und ein größeres Arbeitsbandalphabet den Exponenten um einen konstanten Faktor. Dies reduziert letztendlich den Faktor , aber die untere Raumgrenze ist immer noch . $\delta$ $\Omega(\log n)$

András Salamon
quelle

Vielleicht können wir auf diese Weise eine untere Grenze des -Bereichs für SAT nachweisen (aber ich bin mit der Grenzwert- / asymptotischen Analyse nicht sicher, daher kann meine Antwort völlig falsch sein). $\log n$

Auf einem Turing-Maschinenmodell mit einem schreibgeschützten Eingabeband und einem Arbeitsband, beide über dem binären Alphabet , haben wir für jeden Entscheider mit Zuständen bei einer Eingabe der Größe Folgendes: $\Sigma = \{0,1\}$ $c$ $n$

T (n) \leq c 2^{S (n)} n S (n) (1)

$T(n) \leq c \, 2^{S(n)} \, n \, S(n) \quad (1)$

Andernfalls wird die Turing-Maschine eine Endlosschleife ausführen (die -Komponente repräsentiert alle möglichen Bandkonfigurationen, die Komponente repräsentiert die Eingabebandkopfpositionen, während die -Komponente die Arbeitsbandkopfpositionen repräsentiert). Auf einem Ein-Band-Einzelkopf TM über dem binären Alphabet (1) wird . $2^{S(n)}$ $n$ $S(n)$ $T(n) \leq c 2^{S(n)} S(n)$

Multipliziert man beide Terme mit und wendet den allgemeinen Raum-Zeit-Kompromiss für SAT an, so erhält man: $S(n)$

n^{1.801 + o (1)} \leq S (n) \cdot T (n) \leq c S (n)^{2} 2^{S (n)} n

$n^{1.801+o(1)} \leq S(n)\cdot T(n) \leq c \, S(n)^2 \, 2^{S(n)} \, n$

Die Auswahl einer Leerraumobergrenze wie für SAT würde in der Tat zu einem Widerspruch führen $S(n) \leq (\log n)^{1 - \epsilon}$

lim_{n \to \infty} \frac{n^{1.801}}{c ((\log n)^{1 - ϵ})^{2} 2^{(\log n)^{1 - ϵ}} n} =

$\lim_{n \to \infty} \frac{n^{1.801}}{ c \, ((\log n)^{1-\epsilon})^2 2^{(\log n)^{1-\epsilon}} n } =$

lim_{n \to \infty} (0.801 \cdot \log n - \log c - 2 (1 - ϵ) \log (\log n) - (\log n)^{1 - ϵ}) = \infty

$\lim_{n \to \infty} \Big( 0.801 \cdot \log n - \log c - 2 (1- \epsilon) \log (\log n) - (\log n)^{1-\epsilon}\Big) = \infty$

Marzio De Biasi
quelle

Es scheint mindestens zwei allgemeine Wege zu geben, um zu zeigen, dass eine

-Obergrenze zu einem Widerspruch führt. In erster Linie dachte ich daran, die (im Wesentlichen identische, aber etwas leichter zu bearbeitende) Ungleichung

für eine Konstante

. Der letzte Schritt, den Sie vorsehen, kann auch verstärkt werden, da sich ein Widerspruch auch aus

für

o (\log n)

$o(\log n)$

T (n) \leq 2^{\log n + C . S (n)}

$T(n) \le 2^{\log n + C.S(n)}$

C

$C$

S (n) \leq δ \log n

$S(n) \le \delta\log n$

δ < 0.801 / C

$\delta < 0.801/C$

András Salamon

@ AndrásSalamon: auf der

Seite gebunden ist , kann man nicht einfach Verbesserungen erwartet: von S. Buss und R. Williams. Grenzen für Wechselhandelsnachweise für Zeit-Raum-Untergrenzen, 2012: "Wir zeigen, dass neue Techniken nachweislich notwendig sind, um bessere Zeit-Raum-Untergrenzen für das Erfüllbarkeitsproblem zu beweisen. Das heißt, die Methode des" Wechselhandels " Proofs“verwendet , um festzustellen , dass SAT kann nicht gelöst werden , in

Zeit und

Raum belegen kann keine

S \cdot T

$S\cdot T$

n^{2 \cos (π / 7)}

$n^{2\cos(\pi /7)}$

n^{o (1)}

$n^{o(1)}$

Zeit Untergrenze, für jeden

". Haben Sie eine Idee :-)?

n^{2 \cos (π / 7)} + ϵ

$n^{2\cos(\pi /7)}+\epsilon$

ϵ > 0

$\epsilon >0$

Marzio De Biasi

Ich denke, das ist ungefähr so weit, wie man die Raum-Zeit-Grenzen nutzen kann, gerade weil Ryans Ansatz so weit ist, wie diese Grenzen gehen.

András Salamon

To even store a SAT instance you need

Ω (n)

$\Omega(n)$ and read it you need

Ω (n)

$\Omega(n)$ time. Doesn't this prove

Ω (n^{2})

$\Omega(n^2)$ ST lower bound?

T....

@Turbo, it is not clear that every algorithm to decide SAT has to store the instance: proving an

Ω (n)

$\Omega(n)$ bit deterministic space lower bound would show

L ⊊ N P

$\mathsf{L} \subsetneq \mathsf{NP}$ .

András Salamon