Quantifizierte Boolesche Formeln mit logarithmischen Abwechslungen

Ich untersuche ein Problem, das für die Klasse der quantifizierten Booleschen Formeln mit einer logarithmischen Anzahl von Quantifiziererwechseln schwierig ist. Ein Problem in dieser Klasse würde so aussehen:

$\forall (x_1, x_2, \ldots x_{a_1}) \exists (x_{{a_1}+1}, \ldots x_{a_2}), \ldots \exists(x_{a_{\log n - 1}}, \ldots x_{a_{\log n}})F$

Dabei ist $a_{\log n} = n$ und $F$ eine Boolesche Formel der Variablen $x_1 \ldots x_n$ .

Diese Klasse enthält eindeutig und ist in A P = P S P A C E enthalten . Gibt es einen Namen für diese Klasse? Gibt es etwas mehr darüber bekannt?$PH$$AP = PSPACE$

Aufbauend auf Michael Wehar Antwort, so scheint es , dass man leicht nachweisen kann , dass Berechnungen codiert werden kann in Polygrßenverteilung solche QBFs: Sie verwenden O ( log n ) Abwechslungen, jedes von p o l y ( n ) Bits und tun ein Argument ähnlich wie Satz von Savitch. Alle zwei Wechsel wird die Laufzeit der Berechnung dividieren durch einen p o l y ( $NTISP(n^{\log n},poly(n))$$O(\log n)$$poly(n)$ Faktor.$poly(n)$

Ich würde die Klasse nach der Notation in Fortnows "Time-Space Tradeoffs for Satisfiability" bezeichnen, die auch für das im vorherigen Absatz skizzierte Argument angeführt werden könnte (siehe jedoch das Papier für frühere Verweise).$\Sigma_{O(\log n)} P$

(1) Was wir bereits wissen:

Wie Sie bereits ausgeführt haben, ist QBF mit -Änderungen von Quantifizierern für jede Ebene der Polynomhierarchie schwierig.$\log(n)$

(2) Ich denke, dass wir auch Folgendes beweisen können:

Das Problem ist -hart.$NSPACE(log^2(n))$

(3) Hier ist meine informelle Begründung für die vorhergehende Behauptung:

Wenn ein raumgebundenes NTM und eine Eingabezeichenfolge gegeben sind, müssen wir feststellen, ob für die gegebene Eingabezeichenfolge eine akzeptierende Berechnung existiert.$log^2(n)$

Jede Konfiguration in der Berechnung kann im Wesentlichen durch dargestellt werden Bits dargestellt werden. Mit anderen Worten, wir können eine Konfiguration durch eine Gruppe von log 2 ( n ) -Variablen darstellen.$\log^2(n)$$\log^2(n)$

Die Idee ist, dass wir eine Startkonfiguration und eine Endkonfiguration haben und die Berechnung erraten müssen, die dazwischen stattfindet. Wir erraten rekursiv die "mittleren" Konfigurationen mit existierenden Quantifizierern und verifizieren erneut, dass die "linke" Konfiguration für alle Quantifizierer in die "mittlere" und die "mittlere" Konfiguration in die "rechte" geht.

Damit dies funktioniert, müssen wir statt einer "mittleren" Konfiguration eine Gruppe von "Zwischen" -Konfigurationen mit gleichem Abstand zwischen der "linken" und der "rechten" Konfiguration auswählen. Insbesondere könnten wir √ erraten "Zwischen" -Konfigurationen mit gleichem Abstand unter Verwendung vorhandener Quantifizierer mit$\sqrt{n}$ Variablen und dann für alle Quantifizierer mit ungefähr log ( n ) Variablenauf jede Lücke zwischen Konfigurationen zurückgreifen.$\sqrt{n} * log^2(n)$$\log(n)$

Die Rekursion muss nur bis zur Tiefe fortgesetzt werden werden, um eine Berechnung der Länge √ abdecken zu können$2 * \log(n)$ wobei jede Konfiguration höchstens log 2 (n)viele Bits hat.$\sqrt{n} ^ {2 * \log(n)} = n^{\log(n)} = 2^{\log^2(n)}$$\log^2(n)$

Da die Rekursion die Tiefe , haben wir nur O ( log ( n ) ) Gruppen von Variablen, dh Alternationen. Da jede Gruppe von Quantifizierern nur $O(\log(n))$$O(\log(n))$Variablen, insgesamt haben wirO($\sqrt{n} * log^2(n)$Variablen.$O(\sqrt{n} * log^3(n))$

Fühlen Sie sich frei, Feedback oder Korrekturen anzubieten. Vielen Dank und ich hoffe das hilft ein bisschen.

(4) Eine allgemeinere Behauptung, wie sie in Ryans Antwort vorgeschlagen wird:

Sie sollten in der Lage sein, die vorhergehende Konstruktion allgemeiner auszuführen. Folgendes berücksichtigen:

Teilen Sie bei jedem Schritt der Rekursion mit c in Gruppen von "Zwischen" -Konfigurationen auf$g(n)$ Bits pro Konfiguration auf. Führen Sie dann die Rekursion zur Tiefe d ( n ) durch .$c(n)$$d(n)$

Solange wir nicht zu viele Variablen und zu viele Wechsel haben, scheint dies gut zu funktionieren. Um zufrieden zu sein, müssen wir ungefähr Folgendes tun:

• $g(n) * c(n) * d(n) \leq n$
• $d(n) \leq \log(n)$

Unser verallgemeinerter Ansatz wird verwendet, um nicht deterministische Turing-Maschinen zu simulieren, die unter Verwendung von c ( n ) Speicherbits für Schritte laufen .$g(n)^{d(n)}$$c(n)$

Insbesondere wählen wir Folgendes aus:

• $g(n) = \sqrt{n}$

• $c(n) = \frac{\sqrt{n}}{2 * log^2{n}}$

• $d(n) = 2 * \log^2(n)$

Die vorhergehenden Ungleichungen sind erfüllt und wir können die Konstruktion durchführen, um nicht deterministische Turing-Maschinen zu simulieren, die mit √ für ungefähr Schritte laufen$2^{\log^2(n)}$ Bits an Speicher.$\frac{\sqrt{n}}{2 * log^2{n}}$

Mit anderen Worten, wir haben ein besseres Härteergebnis als zuvor. Insbesondere ist das Problem für N T I S P ( 2 log 2 ( n ) , √ schwer.$NTISP(2^{\log^2(n)}, \frac{\sqrt{n}}{2 * log^2{n}})$

(5) Weitere Verallgemeinerungen:

In der vorangegangenen Verallgemeinerung haben wir nicht deterministische zeit- und raumbegrenzte Turing-Maschinen simuliert. Es kann jedoch auch möglich sein, zeit- und ortsgebundene Turing-Maschinen zu simulieren.

$\log(n)$$\log(n)$$\sqrt{\log(n)}$. Then, we could use the remaining $\sqrt{\log(n)}$ alternations to go to depth $\sqrt{\log(n)}$.

In this case, we could simulate alternating Turing machines that have $\sqrt{\log(n)}$ alternations with sublinear witness lengths, run for $2^{\log^{\frac{3}{2}}(n)}$ steps, and use $\frac{\sqrt{n}}{2 * log^2{n}}$ bits of memory.

In other words, the problem is hard for $AltTimeSpace(\sqrt{\log(n)}, 2^{\log^{\frac{3}{2}}(n)}, \frac{\sqrt{n}}{2 * log^2{n}})$ with sublinear witness lengths. Alternatively, this class could be written using the $STA$ notation mentioned in the comments above.

Thank you for the comments and feel free to offer any further corrections or clarifications. :)

A shorter answer.

Initial observations:

• The problem is hard for every level of the polynomial hierarchy.
• The problem is hard for alternating Turing machines with $\log(n)$ alternations that run for polynomial time.

Deeper Insights:

• Suggested by Kaveh's comment above, the problem can encode computations for $AltTime(\log(n), n)$ Turing machines.
• Also, as Ryan pointed out, the problem can encode computations for $NTimeSpace(2^{\log^2(n)}, \sqrt{n})$ Turing machines.

• More generally, the problem can encode computations for machines corresponding to various classes of the form $AltTimeSpace(a(n), t(n), s(n))$ with restricted witness lengths. I'm not quite sure what the exact relationship between $a(n)$, $t(n)$, and $s(n)$ has to be, but we know that:

  1. $\; \; a(n) \leq \log(n)$

  2. $\; \; t(n) \leq 2^{\log^2(n)}$

  3. $\; \; s(n) \leq n$

See my longer answer for more details on the trade-offs between $a(n)$, $t(n)$, and $s(n)$.

Note: In the above, when I say encode computations, I mean encode the computation without blowing up the instance size too much. That is, if we blow-up from $n$ size Turing machine input to $poly(n)$ size formula, then I think that although the blow-up is polynomial, it is good to pay close attention to the degree of the polynomial. The reason for the semi-fine-grained perspective is to try and slightly better recognize how the different complexity measures $a(n)$, $t(n)$, and $s(n)$ depend on each other.