Więcej na temat PH w PP?

Ostatnie pytanie za pytaniem, czy Huck Bennett PH klasa została zawarta w PP klasy, otrzymał nieco sprzecznych odpowiedzi (wszystko prawda, wydaje się). Z jednej strony podano przeciwnie kilka wyników wyroczni, z drugiej Scott zasugerował, że odpowiedź jest prawdopodobnie pozytywna, ponieważ twierdzenie Tody pokazuje, że PH jest w BP.PP, wariancie probabilistycznym PP, i zazwyczaj uważamy, że randomizacja niewiele pomaga, np. rozsądne założenia dotyczące twardości implikują PRG, które mogą zastąpić randomizację.

Teraz, w przypadku PP, nie jest oczywiste, że nawet „idealny” PRG pociągnie za sobą całkowitą derandomizację, ponieważ naturalna derandomizacja uruchomiłaby oryginalny algorytm z wyjściem PRG dla wszystkich wielomianowo wielu możliwych nasion i uzyskała większość głosów . Nie jest jasne, czy przejęcie tej większości głosów w obliczeniach PP jest czymś, co można zrobić w samym PP. Jednak artykuł Fortnow i Reingold pokazuje, że PP jest zamykany w ramach redukcji tabeli prawdy (przedłużając zaskakujący wynik, że PP jest zamykany na skrzyżowaniu), co wydaje się wystarczające do podjęcia tej większości głosów.

Więc jakie jest tutaj pytanie? Toda, Fortnow-Reingold i wszystkie derandomizacje oparte na PRG wydają się relatywizować, więc sugerowałoby, że PH w PP dla każdej wyroczni, dla której istnieją odpowiednie PRG. Tak więc dla wszystkich wyroczni, pod którymi PP nie zawiera PH (np. Od Minski & Papert, Beigel lub Vereshchagin ), PRG dla PP nie istnieją. W szczególności oznacza to, że dla tych wyroczni nie ma odpowiednio trudnych funkcji w EXP (w przeciwnym razie istniałyby PRG podobne do NW-IW). Patrząc na stronę pozytywną, oznaczałoby to, że gdzieś w każdym z tych wyników wyroczni kryje się (nierównomierny) algorytm PP dla (przybliżenia) EXP z tą wyrocznią. To dziwne, ponieważ wszystkie te wyrocznie wydają się polegać na nowych dolnych granicach PP(dla obwodów progowych) i mają prostą maszynę do budowania wyroczni, więc nie widzę, gdzie kryje się górna granica dla PP. Być może ta górna granica działałaby ogólnie, pokazując, że (nierównomierny) -PP może obliczyć (lub przynajmniej dać pewne odchylenie) wszystkim EXP? Czy coś takiego nie dałoby przynajmniej symulacji CH EXP?

Przypuszczam więc, że moje pytanie jest dwojakie: (1) czy ten łańcuch rozumowania ma sens? (2) Jeśli tak, to czy ktoś może „odkryć” implikowane górne granice PP?

Edytuj przez Aaron Sterling: podbicie tego na pierwszej stronie i dodanie nagrody. To było jedno z moich ulubionych pytań i wciąż nie ma na nie odpowiedzi.

cc.complexity-theory counting-complexity derandomization relativization Noam
źródło

Rzeczywiście zacznij od funkcji boolowskiej w AC0, której nie można obliczyć za pomocą bramki progowej stopnia polilog (N). Dla każdej wyroczni definiujemy język (gdzie to bitów -tego plasterka ). Od , , dla każdego . -tym etapie diagonalizacji wybierze (Dla niektórych ) tak, że -tym PP TM pomyli się na, co dzieje się od czasu

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$ nie jest progiem polilog (N) (jak obliczono w maszynie PP). Więc . Ale może ...

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

Aby uzyskać także , musielibyśmy spakować wiele instancji w jedną długość . Wydaje się to łatwe do wykonania poprzez zdefiniowanie , gdzie dla bitowego ciągu , oznacza bity opisujące, czy dla wszystkich możliwych długości . Musielibyśmy jednak poprawić dolną granicę dla aby wymagać kopii dla różnych

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 łańcuchy nie mogą być obliczane przez bramki progowe polylog (N), nawet z bitami pomocy polylog (N). To powinno być fałszywe dla każdego . Wydaje się, że jest to interesująca górna granica.

f \in A C 0

$f \in AC0$

Noam

Pomyśl o tym, że obserwacja, że pod każdą wyrocznią, która tworzy PH / ⊆ PP, nie ma skutecznych PRG, które oszukują algorytmy BP.PP, nie powinna być bardziej zaskakująca niż fakt, że pod każdą wyrocznią, która czyni BPP / ⊆ P, są brak wydajnych programów PRG, które oszukują algorytmy BPP. To dlatego, że każda wyrocznia, która tworzy PH / ⊆ PP, również tworzy BP.PP / ⊆ PP według twierdzenia Tody (relatywizowanego). Ale może brakuje mi sensu. -

slimton,

Trafne spostrzeżenie. Jednak intuicyjnie, gdy robisz wyrocznię, dla której sedno konstrukcji daje niezwykłą moc, oznacza to także niezwykłą moc dla a tym samym uniemożliwia PRG . Wyrocznią do wydaje się nie dawać żadnych niezwykłą moc do (lub dla każdej grupy), lecz ograniczają moc . Nie jestem jednak pewien, czy tę różnicę można jakoś sformalizować.

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

Jak zauważyłem powyżej: w konstrukcjach dla sedno konstrukcji nadaje BPP (a zatem także P / poli) „nienaturalną” moc, np. Poprzez sadzenie dużej liczby świadków trudnej wyroczni w miejscach, w których tylko randomizacja może je znaleźć. Chociaż jest rzeczywiście interesujące, że ta moc wystarcza na „ogólne” problemy, przynajmniej nieoczekiwana moc P / poli jest oczywista. Z drugiej strony nie widzę nigdzie, że wyrocznia do oddzielania PH od PP daje w rzeczywistości nienaturalną moc P / poly lub jakiejkolwiek innej klasie. Nie jestem jednak pewien, czy ta różnica jest „prawdziwa”.

P \neq B P P

$P \ne BPP$

Noam

Więcej na temat PH w PP?

Odpowiedzi: