P z wyrocznią z faktoryzacji liczb całkowitych

Właśnie przeczytałem pytanie „ Czy rozkład liczb całkowitych jest problemem NP-zupełnym? ” ... więc postanowiłem poświęcić trochę mojej reputacji :-) zadając kolejne pytanie mając :$Q$$P(\text{Q is trivial}) \approx 1$

Jeśli jest wyrocznią, która rozwiązuje faktoryzacji liczb całkowitych, co jest moc P A ? $A$$P^A$

Myślę, że to sprawia, że ​​kryptografia klucza publicznego oparta na RSA jest niepewna ... ale czy oprócz tego istnieją inne niezwykłe wyniki?

Nie mam odpowiedzi na twoje pytanie, ale wiem, że bardzo niedawno badano podobne pojęcie pod nazwą „bezpieczeństwo oparte na aniołach”.

Pierwszym opracowaniem poświęconym tej koncepcji jest Prabhakaran i Sahai (STOC '04) . W szczególności napisali w sposób abstrakcyjny:

[... dajemy] przeciwnikowi dostęp do jakiejś wielobiegunowej mocy obliczeniowej.

Innym ważnym dokumentem omawiającym to pojęcie jest Canetti, Lin i Pass (FOCS 2010) . Obejrzałem niektóre części ich konferencji (na techtalks ) i jeśli dobrze pamiętam, zaczynają od przykładu podobnego do tego, o którym wspomniałeś w pytaniu.

Oczywiście każdy problem decyzyjny, który można sprowadzić do faktorowania, można rozwiązać za pomocą wyroczni faktoringowej. Ale ponieważ mamy możliwość wykonywania wielu zapytań, próbowałem wymyślić nietrywialny problem, dla którego chciałoby się tworzyć wiele zapytań.

Problem obliczania funkcji sumy Eulera wydaje się takim problemem. Nie wiem, jak rozwiązać wersję decyzyjną tego problemu poprzez zmniejszenie Karp do wersji decyzyjnej faktoringu. Ale dzięki redukcjom Turinga łatwo jest zredukować to do faktoringu.

Opracowanie na wcześniejszą odpowiedź Joe: uwaga, że . W tym drugim drugiej najniższej klasy w „niskiej” hierarchii : to znaczy, że N P N P ∩ C O N P = N P . Oznacza to w szczególności, że P FACTORING ⊆ N P Faktoring ⊆ N P . Możemy dokonać Podobne uwagi do c ö N P i B, Q, $\textrm{FACTORING} \in \mathsf{NP \cap coNP}$$\mathsf{NP^{NP \cap coNP} = NP}$

$P^A\subseteq \Delta_2^P$

Cóż, jak zauważyli inni, rozkładanie na czynniki pierwsze $\mbox{FNP}$, więc mamy $P \subseteq P^A \subseteq \Delta_2^p$ (to znaczy $P^{NP}$). Jednak dostępna jest również wersja decyzyjna faktoringu$\mbox{BQP}$, więc w rzeczywistości możemy zrobić trochę lepiej i uzyskać $P \subseteq P^A \subseteq P^{NP \cap BQP}$.