Gibt es einen Zeithierarchiesatz für PH?

Trifft es zu, dass es Probleme in dem Polynom Hierarchie auflösbar in Zeit (durch eine alternierende Turingmaschine in einem bestimmten Ebene der Polynom Hierarchie) , die nicht auflösbar ist in in irgendeine Ebene der Polynom-Hierarchie? Mit anderen Worten - gibt es einen Zeithierarchiesatz für die Polynomhierarchie wie für P und NP? Wenn ja, wäre eine Referenz großartig. $O(n^k)$ $O(n^{k-1})$

Die Schwierigkeit, auf die ich gestoßen bin, besteht darin, dass die simulierende Maschine, wenn sie Maschinen aus allen Hierarchieebenen simuliert, sich nicht in einer bestimmten Hierarchieebene befindet. Was führt zu einer verwandten Frage: Zu welcher kleinsten Klasse gehört eine solche Simulationsmaschine? Hat es einen Sinn, eine Klasse mit Alternationen (oder / ) zu definieren? $O(n)$ $O(\log n)$ $O(\log \log n)$

cc.complexity-theory reference-request polynomial-hierarchy time-hierarchy Joseph
quelle

Die Verwendung einer linearen Anzahl von Alternationen ergibt PSPACE, da die quantifizierte Boolesche Formel PSPACE-vollständig ist.

Derrick Stolee

Antworten:

Ja. Beispielsweise können die üblichen Beweise für die Zeithierarchie Theorem (durch direkte beliebige Maschinen simuliert) verwendet werden , dass für jeden zu zeigen , ist nicht eine Teilmenge von . Der Grund für den Wechsel von zu ist, dass wir in diesem Diagonalisierungsargument das "Gegenteil" der Maschine machen müssen, die wir simulieren, sodass wir im universellen Modus laufen müssen, wenn sich die simulierende Maschine im existenziellen Modus befindet , und umgekehrt. $c \geq 1$ $\Sigma_c TIME[n^k]$ $\Pi_c TIME[n^{k-1}]$ $\Sigma$ $\Pi$

Sie können ein Ergebnis auch erhalten, ohne von zu zu wechseln : Für jedes ist keine Teilmenge von . Dies kann unter Verwendung des Beweises der Zeithierarchie nach Zak erfolgen (Referenz: " A Turing machine time hierarchy ", Theoretical Computer Science 26 (3): 327-333, 1983). Für einen expliziten Verweis auf diese Version des Zeithierarchiesatzes siehe Dieter van Melkebeeks " Eine Übersicht über niedrigere Grenzen für Erfüllbarkeit und verwandte Probleme " (verfügbar auf seiner Homepage). $\Sigma$ $\Pi$ $c \geq 1$ $\Sigma_c TIME[n^k]$ $\Sigma_c TIME[n^{k-1}]$

Ryan Williams
quelle

Diese Antwort zeigt sehr deutlich die Existenz eines Zeithierarchiesatzes für jede einzelne Ebene der Hierarchie. Dies zeigt nicht sofort das Vorhandensein eines solchen Satzes für PH als Ganzes.

Joseph

Ihre stärkere Frage wird schwer zu bejahen sein; es würde bedeuten, . Angenommen, es gibt ein und eine Sprache in , die nicht in für jedes . Dann . Dies liegt daran, dass jede Sprache für einige in abhängig von (durch ein Argument vom Typ Savitch-Theorem). Also, wenn dann ist tatsächlich jede Sprache in für einige in

L O G S P A C E \neq N P

$LOGSPACE \neq NP$

c

$c$

L

$L$

Σ_{c} T I M E [n^{k}]

$\Sigma_c TIME[n^k]$

Σ_{d} T I M E [n^{k - 1}]

$\Sigma_d TIME[n^{k-1}]$

d

$d$

L O G S P A C E \neq N P

$LOGSPACE \neq NP$

L \in L O G S P A C E

$L \in LOGSPACE$

Σ_{d} T I M E [n^{2}]

$\Sigma_d TIME[n^2]$

d

$d$

L

$L$

L O G S P A C E = N P

$LOGSPACE = NP$

Σ_{c} T I M E [n^{k}]

$\Sigma_c TIME[n^k]$

Σ_{d} T I M E [n^{2}]

$\Sigma_d TIME[n^2]$

d

$d$ , im Widerspruch zu dem, was Sie zeigen möchten.

Ryan Williams

Die Antwort auf die überarbeitete Frage (Revision 4 der Frage) lautet nein. Wenn ein Entscheidungsproblem L in der Zeit O ( n ^k ) von einer ∑ _i P-Maschine lösbar ist , dann kann L in linearer Zeit von einer Turing-Maschine mit dem Orakel für L gelöst werden , das eine ∑ _{i +1} P-Maschine ist. Daher Σ _i Zeit [O ( n ^k )] ⊆ Σ _{i +1} Zeit [O ( n )].

Tsuyoshi Ito
quelle

Nein, so funktioniert die Definition von . Wenn für alle , dann . Wenn und für jedes , sei die Laufzeit von ein nichtdeterministischer Algorithmus für die Tautologie. Dann haben wir , wobei die erste Einbeziehung nach erfolgt Annahme und der zweite Einschluss ergeben sich aus einem Standard-Simulationsargument. Das ist ein Widerspruch.

Σ_{j} T I M E [t (n)]

$\Sigma_j TIME[t(n)]$

Σ_{j} T I M E [O (n^{k})] \subseteq Σ_{j + 1} T I M E [O (n)]

$\Sigma_j TIME[O(n^k)] \subseteq \Sigma_{j+1} TIME[O(n)]$

j, k

$j,k$

N P \neq c o N P

$NP \neq coNP$

N P = c o N P

$NP = coNP$

Σ_{j} T I M E [O (n^{k})] \subseteq Σ_{j + 1} T I M E [O (n)]

$\Sigma_j TIME[O(n^k)] \subseteq \Sigma_{j+1} TIME[O(n)]$

j, k

$j,k$

O (n^{c})

$O(n^c)$

N T I M E [O (n^{c^{2}})] \subseteq Σ_{2} T I M E [O (n)] \subseteq N T I M E [O (n^{c})]

$NTIME[O(n^{c^2})] \subseteq \Sigma_{2} TIME[O(n)] \subseteq NTIME[O(n^{c})]$

Ryan Williams

@Ryan: Die Definition, die ich verwendet habe, ist: L∈ΣiTIME [t (n)] falls es eine Sprache O∈Σ (i − 1) P und eine nicht deterministische t (n) -Zeit-Turingmaschine mit dem Orakel für O gibt, das erkennt L. Ich dachte, dass dies die Standarddefinition ist, habe aber keinen Hinweis, um meinen Anspruch zu belegen. Welche Definition verwenden Sie?

Tsuyoshi Ito

Die Definition lautet: falls es ein lineares so dass ist wahr.

L \in Σ_{i} T I M E [t (n)]

$L \in \Sigma_i TIME[t(n)]$

R (x, y_{1}, \dots, y_{i})

$R(x,y_1,\ldots,y_i)$

x \in L ⟺ (\exists y_{1} : | y_{1} | \leq t (| x |)) \dots (\forall y_{i} : | y_{i} | \leq t (| x |)) R (x, y_{1}, \dots, y_{i})

$x \in L \iff (\exists y_1 : |y_1|\leq t(|x|))\cdots (\forall y_i : |y_i| \leq t(|x|))R(x,y_1,\ldots,y_i)$

Ryan Williams

@ Ryan: Ok, ich kannte diese Definition nicht. Wenn der Fragesteller danach fragen wollte, trifft meine Antwort nicht zu.

Tsuyoshi Ito