Gibt es einen Zeithierarchiesatz für PH?

18

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 - 1 )O(nk)O(nk1)

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 / O (\ log \ log n) ) zu definieren?O ( log n ) O ( log log n )O(n)O(logn)O(loglogn)

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

Antworten:

17

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 T I M E [ n k ] Π c T I M E [ n k - 1 ] Σ Πc1ΣcTIME[nk]ΠcTIME[nk1]ΣΠ

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).& Pgr; c 1 Σ c T I M E [ n k ] Σ c T I M E [ n k - 1 ]ΣΠc1ΣcTIME[nk]ΣcTIME[nk1]

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
4
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 inc L Σ c T I M E [ n k ] Σ d T I M E [ n k - 1 ] d L O G S P A C E N P L L O G S P A C E Σ d T ILOGSPACENPcLΣcTIME[nk]ΣdTIME[nk1]dLOGSPACENPLLOGSPACEd L L O G S P A C E = N P Σ c T I M E [ n k ] Σ d T I M E [ n 2 ] dΣdTIME[n2]dLLOGSPACE=NPΣcTIME[nk]ΣdTIME[n2] d , im Widerspruch zu dem, was Sie zeigen möchten.
Ryan Williams
3

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
1
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. ΣjTIME[t(n)]ΣjTIME[O(nk)]Σj+1TIME[O(n)]j,kNPcoNPNP=coNPΣjTIME[O(nk)]Σj+1TIME[O(n)]j,kO(nc)NTIME[O(nc2)]Σ2TIME[O(n)]NTIME[O(nc)]
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
1
Die Definition lautet: falls es ein lineares so dass ist wahr. R ( x , y 1 , ... , y i ) , x LLΣiTIME[t(n)]R(x,y1,,yi)xL(y1:|y1|t(|x|))(yi:|yi|t(|x|))R(x,y1,,yi)
Ryan Williams
@ Ryan: Ok, ich kannte diese Definition nicht. Wenn der Fragesteller danach fragen wollte, trifft meine Antwort nicht zu.
Tsuyoshi Ito