Więcej na temat PH w PP?

63

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.

Noam
źródło
2
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 czasuA L A = { 1 n | f ( A n ) = 1 } A n 2 n n A f A C 0 L AP H A A t A n n t 1 nL A ? f L.f:{0,1}N{0,1}ALA={1n|f(An)=1}An2nnAfAC0LAPHAAtAnnt1nLA?fnie jest progiem polilog (N) (jak obliczono w maszynie PP). Więc . Ale może ...L AP P A | p o l yLAPPALAPPA|poly
Noam
2
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óżnychf n L A = { x | f ( A x ) = 1 } n x A x 2 n x y A 2 n y n f N f N f A C 0LAPPA/polyfnLA={x|f(Ax)=1}nxAx2nxyA2nynfNfN-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. fAC0
Noam
1
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,
1
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ć. B P P A P A / p o l y P H AP P APABPPABPPAPA/polyPHAPPA P P APAPPA
Noam
1
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”. PBPP
Noam

Odpowiedzi:

9

Dzięki pracy Klivansa i van Melkebeeka (który relatywizuje), jeśli E = DTIME ( ) nie ma obwodów z bramkami PP wielkości wówczas PH jest w PP. Przeciwnie, mówi się, że jeśli PH nie jest w PP, wówczas E ma obwody podwykładnicze z bramkami PP. Jest to zgodne z faktem, że dowód na wyrocznię dla PH nie w PP daje relatywną dolną granicę dla PP. Nie ma powodu, aby sądzić, że implikuje to górną granicę dla PP lub jakąkolwiek siłę dla obwodów bez bram PP. 2 o ( n )2O(n)2o(n)

Lance Fortnow
źródło
Poprawny. Naprawiony.
Lance Fortnow