Quantifizierte Boolesche Formeln mit logarithmischen Abwechslungen

15

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:

(x1,x2,xa1)(xa1+1,xa2),(xalogn1,xalogn)F

Dabei ist alogn=n und F eine Boolesche Formel der Variablen x1xn .

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?PHAP=PSPACE

isaacg
quelle
3
Nun, es ist vollständig für den Wechsel der Polynomzeit mit logarithmisch vielen Abwechslungen.
Emil Jeřábek unterstützt Monica
2
Eine vereinbarte Notation für die Komplexitätsklasse dieses Problems wäre STA ( ). Hier ist STA (s (n), t (n), a (n)) das von Berman in "Die Komplexität logischer Theorien", das 1980 in TCS erschien, eingeführte Raum-Zeit-Wechselmaß. Diese Klasse enthält alle Entscheidungen Problem, das durch eine alternierende Turing-Maschine in der Zeit t (n) unter Verwendung des Raums s (n) und höchstens a (n) mal in jedem Berechnungszweig entscheidbar ist. Wie Emil betonte, sollte Ihr Problem für diese Klasse vollständig sein. ,nO(1),O(logn)
Christoph Haase
2
AltTime (lg n, poly (n))
Kaveh
Ist es nicht auch das binäre Analogon der von Barrington, Kadau, McKenzie und Lange eingeführten Klasse FOLL? FOLL wird durch n-maliges Iterieren eines FO-Blocks definiert. Es ist zu schwach, um die Parität zu berechnen, aber es ist nicht bekannt, dass es in einer Klasse enthalten ist, die kleiner als AC ^ 1 ist. Es kann eine Reihe nicht-trivialer Aufgaben ausführen, einschließlich des Einschaltens einer kommutativen Gruppe, die als Multiplikationstabelle dargestellt wird. Ich möchte die betreffende Klasse PHL nennen, da sie einem PH-Block entspricht, der n-mal loggt. Ich denke, es ist immer noch nicht klar, ob es mit PSPACE vergleichbar ist.
SamiD
Auch wenn eine abelsche Gruppe durch eine Schaltung gegeben ist, die zwei n-Bit-Zahlen eingibt und eine n-Bit-Zahl ausgibt, erfolgt die Energieversorgung in PHL durch einen ähnlichen Beweis wie bei Barrington et al. Oben.
SamiD

Antworten:

7

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 ( nNTISP(nlogn,poly(n))O(logn)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).ΣÖ(Logn)P

Ryan Williams
quelle
Vielen Dank für den Kommentar und die Antwort. Ich habe meine Antwort bearbeitet und Details zur Verallgemeinerung des Arguments hinzugefügt. Tatsächlich gibt es einen Kompromiss zwischen Zeit, Raum und Wechsel für die Arten von Berechnungen, die codiert werden können.
Michael Wehar
Vielen Dank für den Hinweis! Außerdem habe ich eine prägnantere Antwort hinzugefügt, um dies hoffentlich zu klären. Danke noch einmal. :)
Michael Wehar
7

(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(log2(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.log2(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.log2(n)log2(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 mitn Variablen und dann für alle Quantifizierer mit ungefähr log ( n ) Variablenauf jede Lücke zwischen Konfigurationen zurückgreifen.nlog2(n)log(n)

Die Rekursion muss nur bis zur Tiefe fortgesetzt werden werden, um eine Berechnung der Länge abdecken zu können2log(n) wobei jede Konfiguration höchstens log 2 (n)viele Bits hat.n2log(n)=nlog(n)=2log2(n)log2(n)

Da die Rekursion die Tiefe , haben wir nur O ( log ( n ) ) Gruppen von Variablen, dh Alternationen. Da jede Gruppe von Quantifizierern nur √ hatO(log(n))O(log(n))Variablen, insgesamt haben wirO(nlog2(n)Variablen.O(nlog3(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 aufg(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)n
  • d(n)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)=n

  • c(n)=n2log2n

  • d(n)=2log2(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 laufen2log2(n) Bits an Speicher.n2log2n

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(2log2(n),n2log2n)

(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)log(n). Then, we could use the remaining log(n) alternations to go to depth log(n).

In this case, we could simulate alternating Turing machines that have log(n) alternations with sublinear witness lengths, run for 2log32(n) steps, and use n2log2n bits of memory.

In other words, the problem is hard for AltTimeSpace(log(n),2log32(n),n2log2n) 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. :)

Michael Wehar
quelle
1
Wouldn't the NL2-hardness follow straightaway from PH-hardness?
Nikhil
1
How exactly do we know point (1)? Don't we need 2k variables to get to some level k of PH? Maybe I'm missing a simple point here.
Markus
1
@MichaelWehar Sure, but we do know that NL2PH right? And that means every problem in NL2 reduces to QBF with constantly many alternations, which is a special case of log-many alternations?
Nikhil
1
@MichaelWehar Oops. Of course you're right! A related question here: cstheory.stackexchange.com/questions/14159/…
Nikhil
2
Why not NTISP(nlogn,poly(n))-hard?
Ryan Williams
1

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(2log2(n),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)log(n)

    2. t(n)2log2(n)

    3. s(n)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.

Michael Wehar
quelle
Also, there is another factor that I omitted. That is, the witness size used with each alternation takes up variables. In other words, the larger the witnesses, the fewer variables that we have meaning that potentially we can't represent as many bits per configuration causing us to possibly require there to be less space for the machine that we encode computations for.
Michael Wehar
Basically, all witness lengths for the quantifiers are sublinear and how large we can make them depends on the choice of a(n), t(n), and s(n).
Michael Wehar
Maybe an inner most there exists quantifier doesn't need to have restricted witness size because we can guess as we go.
Michael Wehar