Uneinheitliche Version für die gesamte Polynomhierarchie

8

Die ungleichmäßigen Versionen von P, NP und coNP sind P / Poly, NP / Poly und coNP / Poly. Ebenso können wir für jede Ebene in der PH eine ungleichmäßige Version definieren.

Zum Beispiel: / poly von Problemen der Form besteht { x : y zΣ2 , wobei C eine Schaltung mit Polynomgröße ist, die abhängig von der Länge der Eingabezeichenfolge x variieren kann, und y , z auch Polynomlängen in x haben .{x:yzC(x,y,z)}xy,zx

Wenn wir dies für alle PH-Stufen tun, erhalten wir eine ungleichmäßige Version von PH / Poly.

FRAGEN: Ist etwas über diese Hierarchie bekannt? Bricht es zusammen? Oder gibt es dafür einen anderen Namen in der Literatur?

Danny Nguyen
quelle

Antworten:

6

Na klar, wir wissen Dinge. Ich denke, das ist eine ziemlich normale Nomenklatur dafür. Diese Hierarchie zusammenbricht , wenn und nur wenn der Fall ist, Übung:PH

  • Ändern Sie für eine Richtung den Beweis von Karp-Lipton, um zu zeigen, dass, wenn ist, P H zusammenbricht, und beobachten Sie, dass sich dieses Ergebnis relativiertNPcoNP/polyPH
  • Für die andere Richtung siehe die Kommentare von Kaveh unten.
Joshua Grochow
quelle
1
PHnuPH
1
@ Daniel, ich denke, Sie können die Gleichmäßigkeit der Quantifizierer in der Schaltung beseitigen, also ja, wenn PH sie kollabiert, tut dies auch nuPH.
Kaveh
2
@ Kaveh: Wie? Ich mag langsam sein, aber ich sehe es noch nicht ...
Joshua Grochow
4
ΣkPχL(x)=χL(x,f(|x|))ΣkP
3
PH/poly