P z wyrocznią z faktoryzacji liczb całkowitych

18

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 ? $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?

cc.complexity-theory oracles factoring

— Marzio De Biasi
źródło

3

@Czy ta część P(Q is trivial)=1jest żartem, prawda?

— Pratik Deoghare

To pytanie sugeruje powiązane i (być może) bardziej naturalne pytanie: jeśli R jest wyrocznią, która zwraca f _ (_ M , n ) jako maksymalny czas działania maszyny Turinga wielomianowego M na wszystkich wejściach długości n , jaka jest moc P ^ R?

— John Sidles,

2

@Vor: Czy to nie to samo, co pytanie „Które problemy mogą być wielomianowe w czasie Turinga redukują do faktoryzacji liczb całkowitych?” A może chciałeś zapytać o coś jeszcze?

— Joshua Grochow

Jestem nowicjuszem, więc moje pytanie jest prawie ciekawostką. Wszystko zaczęło się od prostej myśli: „w prawdziwym świecie” widzę wiele problemów z NP-listonoszem (listonosz próbuje zachować swoją siłę, rodzina, która się porusza i chce zmieścić swoje meble w ciężarówce, ...: - ))). Ale nie widzę „problemów z faktoringiem” ... chociaż MOGĄ być prostsze (między P i NPC). ... może rzeczywistość nie znosi mnożenia :-D :-D

— Marzio De Biasi

1

Zobacz także Konsekwencje faktoringu w P?

— Jukka Suomela

11

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.

— MS Dousti
źródło

13

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.

— Robin Kothari
źródło

3

Oto powiązany post w MO dotyczący złożoności obliczania funkcji totalnej.

— Hsien-Chih Chang 8 之

Mały dodatek: istnieją również wielomianowe skrócenie czasu w innym kierunku, obliczając funkcję Eulera Totient -> Faktoring. Nie sprawdziłem jednak, czy znane redukcje działają w przypadku decyzyjnej wersji tych problemów. Mimo to, możliwość obliczenia funkcji Totient (lub nawet jej ustalonej wielokrotności) daje możliwość faktoryzacji. Książka Shoup poświęca temu rozdział.

— Juan Bermejo Vega

9

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

P^{FACTORING} \subseteq N P^{FACTORING} \subseteq N P .

$\mathsf{P^{\textrm{FACTORING}} \subseteq NP^{\textrm{FACTORING}}} \subseteq \mathsf{NP}.$

c o N P

$\mathsf{coNP}$

B Q P

$\mathsf{BQP}$ I wskazują, że co najmniej na poziomie gruboziarnisty,

ma takie same granice złożoności jako problem

siebie, co znaczy

P^{FACTORING}

$\mathsf P^{\textrm{FACTORING}}$

FACTORING

$\textrm{FACTORING}$

P^{FACTORING} \subseteq N P \cap c o N P \cap B Q P .

$\mathsf{P^{\textrm{FACTORING}} \subseteq NP \cap coNP \cap BQP}.$

— Niel de Beaudrap
źródło

N P \cap c o N P

$NP \cap coNP$

3

U P \cap c o U P

$\mathsf{UP} \cap \mathsf{coUP}$

6

$P^A\subseteq \Delta_2^P$

— Marcus Ritt
źródło

5

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}$ .

— Joe Fitzsimons
źródło