Mehr zu PH in PP?

Eine kürzlich von Huck Bennett gestellte Frage, ob die Klasse PH in der Klasse PP enthalten ist, erhielt etwas widersprüchliche Antworten (alles scheint wahr zu sein). Einerseits wurden mehrere Orakelergebnisse für das Gegenteil angegeben, und andererseits schlug Scott vor, dass die Antwort wahrscheinlich positiv ist, da Todas Theorem zeigt, dass PH in BP.PP, der probabilistischen Variante von PP, enthalten ist, und wir glauben normalerweise, dass dies bei der Randomisierung der Fall ist hilft nicht viel, zB implizieren vernünftige Härteannahmen PRGs, die die Randomisierung ersetzen können.

Nun ist im Fall von PP nicht von vornherein klar, dass selbst ein "perfektes" PRG eine vollständige Derandomisierung impliziert, da die natürliche Derandomisierung den ursprünglichen Algorithmus mit der Ausgabe des PRG für alle polynomiell vielen möglichen Samen ausführen und eine Mehrheitsabstimmung treffen würde . Es ist nicht klar, dass die Mehrheitsentscheidung unter den PP-Berechnungen in PP selbst durchgeführt werden kann. Ein Artikel von Fortnow und Reingold zeigt jedoch, dass PP unter Reduktion der Wahrheitstabelle geschlossen ist (was das überraschende Ergebnis erweitert, dass PP unter Verschneidung geschlossen ist), was für die Annahme dieser Mehrheitsabstimmung ausreicht.

Also, was ist die Frage hier? Toda, Fortnow-Reingold und alle PRG-basierten Derandomisierungen scheinen sich zu relativieren, was impliziert, dass PH in PP für jedes Orakel, für das entsprechende PRGs existieren. Für alle Orakel, unter denen PP kein PH enthält (z. B. von Minski & Papert, von Beigel oder von Vereshchagin ), gibt es keine PRGs für PP. Dies impliziert insbesondere, dass es für diese Orakel keine angemessen harten Funktionen in EXP gibt (andernfalls würden NW-IW-ähnliche PRGs existieren). Wenn man die positive Seite betrachtet, würde dies bedeuten, dass sich irgendwo in jedem dieser Orakelergebnisse ein (uneinheitlicher) PP-Algorithmus zur (Approximation) der EXP mit diesem Orakel verbirgt. Dies ist seltsam, da all diese Orakelergebnisse auf neuen PP- Untergrenzen beruhen(für Schwellenwert-Schaltkreise) und sind unkompliziert in ihren Orakelbaumaschinen, sodass ich nicht sehe, wo sich eine Obergrenze für PP verbirgt. Vielleicht würde diese obere Schranke im Allgemeinen funktionieren und zeigen, dass (uneinheitliche) -PP die gesamte EXP berechnen kann (oder zumindest eine gewisse Verzerrung ergibt)? Würde so etwas nicht zumindest eine CH-Simulation von EXP geben?

Ich nehme also an, meine Frage ist zweifach: (1) Ist diese Argumentationskette sinnvoll? (2) Wenn ja, kann jemand die implizierten Obergrenzen für PP "aufdecken"?

Edit von Aaron Sterling: Stoße dies auf die Titelseite und füge ein Kopfgeld hinzu. Dies war eine meiner Lieblingsfragen, auf die es immer noch keine Antworten gibt.

cc.complexity-theory counting-complexity derandomization relativization Noam
quelle

Beginnen Sie in der Tat mit einer Booleschen Funktion in AC0, die von einem Polylog (N) -Grad-Schwellwertgatter nicht berechnet werden kann. Für jedes Orakel definieren wir die Sprache (wobei die Bits der -ten Schicht von ). Da , , für alle . Der -te diagonalization Schritt wählt (für einige ) , so dass der -ten PP TM macht einen Fehler auf, was passiert seit

f : {0, 1}^{N} \to {0, 1}

$f:\{0,1\}^N \rightarrow \{ 0,1\}$

A

$A$

L_{A} = {1^{n} | f (A_{n}) = 1}

$L_A= \{1^n | f(A_n)=1\}$

A_{n}

$A_n$

2^{n}

$2^n$

n

$n$

A

$A$

f \in A C 0

$f \in AC0$

L_{A} \in P H^{A}

$L_A \in PH^A$

A

$A$

t

$t$

A_{n}

$A_n$

n

$n$

t

$t$

1^{n} \in L_{A} ?

$1^n \in L_A?$

f

$f$ ist nicht Polylog (N) -Schwelle (wie die Berechnung einer PP-Maschine ist). So . Aber vielleicht ...

L_{A} \notin P P^{A}

$L_A \not\in PP^A$

L_{A} \in P P^{A} | p o l y

$L_A \in PP^A|poly$

Noam

Um also auch , müssten wir viele Instanzen von in eine einzige Länge packen . Dies scheint einfach zu indem , wobei für eine - Bit Zeichenkette , bezeichnet die -bits beschreibt , ob für alle möglich ‚s der Länge . Aber wir müssten die Untergrenze für verbessern, um zu fordern, dass Kopien von auf verschiedenen

L_{A} \notin P P^{A} / p o l y

$L_A \not\in PP^A/poly$

f

$f$

n

$n$

L_{A} = {x | f (A_{x}) = 1}

$L_A = \{ x | f(A_x)=1\}$

n

$n$

x

$x$

A_{x}

$A_x$

2^{n}

$2^n$

x y \in A

$xy \in A$

2^{n}

$2^n$

y

$y$

n

$n$

f

$f$

N

$N$

f

$f$

N

$N$ -Bit-Strings können nicht mit Polylog (N) -Schwellengattern berechnet werden, auch nicht mit Polylog (N) -Hilfebits. Dies sollte also für jedes . Eine interessante Obergrenze, wie es scheint.

f \in A C 0

$f \in AC0$

Noam

Man denke nur an die Beobachtung, dass es unter jedem Orakel, das PH / ⊆ PP erzeugt, keine effizienten PRGs gibt, die BP.PP-Algorithmen zum Narren halten, und dass es unter jedem Orakel, das BPP / ⊆ P erzeugt, keine überraschenderen gibt Keine effizienten PRGs, die BPP-Algorithmen täuschen. Das liegt daran, dass jedes Orakel, das PH / ⊆ PP macht, auch BP.PP / ⊆ PP nach Todas Theorem (relativiert) macht. Aber vielleicht verpasse ich den Punkt. -

Slimton

Das ist ein guter Punkt. Intuitiv, wenn Sie ein Orakel machen, für das der Kern der Konstruktion ist, gibt eine ungewöhnliche Kraft, so dass auch ungewöhnliche Kraft erhält und PRGs somit unmöglich werden . Das Orakel für scheint (oder einer Klasse) keine ungewöhnliche Kraft zu verleihen, sondern die Kraft von zu begrenzen . Ich bin mir jedoch nicht sicher, ob dieser Unterschied irgendwie formalisiert werden kann.

P^{A} \neq B P P^{A}

$P^A \ne BPP^A$

B P P^{A}

$BPP^A$

P^{A} / p o l y

$P^A/poly$

P H^{A} ⊈ P P^{A}

$PH^A \not\subseteq PP^A$

P^{A}

$P^A$

P P^{A}

$PP^A$

Noam

Wie ich oben bemerkte: In den Konstruktionen für der Kern der Konstruktion BPP (und damit auch P / poly) "unnatürliche" Kraft, indem z. B. viele Zeugen für das harte Orakel an Orten gepflanzt werden, an denen nur Randomisierung kann sie finden. Während es in der Tat interessant ist, dass diese Potenz für "allgemeine" Probleme ausreicht, ist zumindest die unerwartete Potenz von P / poly klar. Andererseits kann ich nirgendwo erkennen, dass das Orakel für die Trennung von PH und PP P / Poly oder einer anderen Klasse eine unnatürliche Kraft verleiht. Ich bin mir nicht sicher, ob dieser Unterschied "echt" ist.

P \neq B P P

$P \ne BPP$

Noam

Mehr zu PH in PP?

Antworten: