Trennung von Klassen mit unterschiedlichen Ratschlägen?

9

Mit dem Zeithierarchiesatz kann man zeigen, dass es beispielsweise Probleme in P gibt, die von einer Turing-Maschine nicht in einer Zeit gelöst werden können, die kleiner als const * n ^ 2 ist. Aber geben Sie der Turing-Maschine einige Ratschläge und alle Wetten sind geschlossen. Man kann noch nicht zeigen, dass selbst eine Schaltung mit linearer Größe nicht den gesamten PSPACE lösen kann. Was ist, wenn wir versuchen, zwei verschiedene Klassen zu vergleichen, in denen beide Ratschläge haben? Kann man zum Beispiel den Polynomraum mit logarithmischer Beratung von der linearen Zeit mit linearer Beratung trennen? Das ist nur eine erfundene Beispielfrage. Ich frage mich, welche allgemeinen Ergebnisse es in dieser Richtung gibt.

matte Hastings
quelle
@Tsuyoshi: Ich habe das [advice]Tag hinzugefügt und einige Änderungen vorgenommen (z. B. Satzmathematik), aber das OP hat meine Änderungen rückgängig gemacht! Vielen Dank, dass Sie die richtigen Tags erneut hinzugefügt haben.
MS Dousti
Entschuldigung, ich habe den Rollback durchgeführt, da die gesetzte Mathematik etwas schwer zu lesen war, aber danke für das Tag.
Matt Hastings
@Sadeq: Ich habe die Tags [Ratschläge] und [Trennung] hinzugefügt, ohne den Verlauf zu bemerken. Danke für den Hinweis!
Tsuyoshi Ito

Antworten:

5

Sei eine Funktion. Es kann nachgewiesen werden, dass:s(n)n

DSIZE(s)DTIME(s2)/F(O(slogs))

DSIZE(s)sK/FKF

F(f)={h:{0,1}{0,1}|h(x)|f(|x|) for all x}

d(n)logn

DDEPTH(d)DSPACE(d)/F(2O(d))

DDEPTH(d)d


Edit: zwei weitere Einschlüsse:

t(n)nDTIME(t)DSIZE(tlogt)l(n)lognNSPACE(l)DDEPTH(l2)


Beweise finden Sie in Abschnitt 2-3 von Heribert Vollmers Buch .

Mit diesen Einschlüssen und Zeit- / Raumhierarchien können Hierarchien für ungleichmäßige Komplexitätsklassen erstellt werden.


Bearbeiten 2:

Sie können die obigen Ergebnisse mit den folgenden Ergebnissen zu Hierarchien für Klassen mit Ratschlägen kombinieren:

  1. Zeithierarchien für Berechnungen mit ein wenig Rat .
  2. Bedingungslose Untergrenzen gegen Rat .
MS Dousti
quelle
Ich bin mir nicht sicher, ob dies die Frage beantwortet. Es setzt Schaltkreise in Sprachen mit Ratschlägen (was ich implizit getan habe und ist ziemlich klar, warum es wahr ist), beantwortet aber nicht (es sei denn, ich vermisse etwas?) Die Frage, wie man die Trennung bekommt? Ich meine, Sie erwähnen Zeit- / Raumhierarchien, aber was sind dann die bekannten Hierarchien für Klassen mit Ratschlägen?
Matt Hastings
@matt: Überprüfen Sie, ob die bearbeitete Antwort Ihren Anforderungen entspricht.
MS Dousti
Das ist die Art von Sache, die ich suche, danke.
Matt Hastings