vs

Czy ? Lub, bardziej ogólnie, czy ? $\mathsf{NP^{PP}} = \mathsf{P^{PP}}$ $\mathsf{NP^{PP}} \subseteq \mathsf{P^{PP}/poly}$

complexity-classes

— Ilja Wołkowicz
źródło

To są interesujące otwarte problemy. Twoje drugie pytanie powoduje upadek Karp-Lipton.

Zauważ, że twierdzenie Tody daje ci , ale to nie wystarcza do naszych celów. Chcemy wiedzieć, czy , co sprawia, że jest to śmieszne pytanie w mojej opinii. $NP\subseteq P^{PP}$ $NP^{PP}\subseteq P^{PP}$

1: Zauważ, że $NP^{PP}=NP^{\#P}$ i , więc twoje pierwsze pytanie zostało już zadane i odpowiedziano tutaj . Twój pyta czy wielomian hierarchia zapada w stosunku do wyroczni (lub równoważnie względem Oracle). Zgodnie z tą odpowiedzią jest to pytanie otwarte. Jeśli wówczas hierarchia ulega załamaniu w stosunku do tej wyroczni. $P^{PP}=P^{\#P}$ $PP$ $\#P$ $P^{PP}=NP^{PP}$

2: Myślę, że jest otwartym problemem, a byłoby odpowiedzieć, jeśli wiemy, czy wielomian hierarchia zapada w stosunku do wyroczni. Ponieważ pamiętaj, że występuje zawalenie się Karp-Lipton: $PP$

tu tylko używane z faktu, że Karp-Lipton twierdzenie relatywizująca. To, czy postrzegasz to jako dowód przeciw przypuszczeniu, zależy od tego, czy uważasz, że hierarchia wielomianowa zawala się w stosunku do , ponieważ jeśli uważasz, że zapada się aż do stosunku do tej wyroczni, to tak,

N P^{P P} \subset P_{/ p o l y}^{P P} implies {Σ_{2}^{P}}^{P P} = {Π_{2}^{P}}^{P P}

$NP^{PP}\subset P^{PP}_{/poly} \text{ implies }{\Sigma_2^P}^{PP}={\Pi_2^P}^{PP}$

P P

$PP$

P

$P$

N P^{P P} = P^{P P} \subset P_{/ p o l y}^{P P}

$NP^{PP}=P^{PP}\subset P^{PP}_{/poly}$

Idąc dalej, należy pamiętać, że a nie mamy wyroczni, która oddziela , więc wyrocznia kierunku twoje pierwsze pytanie, , jest bardziej ambitne i samo w sobie byłoby dobrym wynikiem. Obecnie nie mamy nawet wyroczni, w stosunku do której

P P \subseteq P^{P P} \subseteq N P^{P P} \subseteq P P^{P P} = C_{2}^{P},

$PP\subseteq P^{PP}\subseteq NP^{PP}\subseteq PP^{PP}=C_2^P,$

P P ⊊ P P^{P P}

$PP\subsetneq PP^{PP}$

P^{P P} ⊊ N P^{P P}

$P^{PP}\subsetneq NP^{PP}$

P^{P P} ⊊ P S P A C E

$P^{PP}\subsetneq PSPACE$

Osobiście chciałbym zobaczyć drugą stronę: czy ? Wiemy już, że nie jest zawarte w dla żadnego ustalonego . Czy możemy to samo pokazać dla ? $PP\subseteq NP_{/poly}$ $PP$ $P_{/n^k}$ $k$ $NP_{/n^k}$

— Lieuwe Vinkhuijzen
źródło