P mit ganzzahligem Faktorisierungsorakel

18

Ich habe gerade die Frage " Ist die Faktorisierung von Ganzzahlen ein NP-vollständiges Problem? " Gelesen, also habe ich mich entschlossen, einen Teil meines Rufs auszugeben :-) und eine andere Frage gestellt: mit : $Q$ $P(\text{Q is trivial}) \approx 1$

Wenn ein Orakel ist, das die ganzzahlige Faktorisierung löst, was ist die Kraft von ? $A$ $P^A$

Ich denke, es macht RSA-basierte Public-Key-Kryptografie unsicher ... aber abgesehen davon gibt es noch andere bemerkenswerte Ergebnisse?

cc.complexity-theory oracles factoring Marzio De Biasi
quelle

3

@Vor diesem Teil P(Q is trivial)=1ist ein Witz, nicht wahr ?

Pratik Deoghare

Diese Frage schlägt eine verwandte und (vielleicht) natürlichere Frage vor: Wenn R ein Orakel ist, das f _ (_ M , n ) als die maximale Laufzeit einer Polynomzeit-Turing-Maschine M über alle Eingaben der Länge n zurückgibt , wofür ist die Potenz von P ^ R?

John Sidles

2

@Vor: Ist das nicht dasselbe wie die Frage "Welche Probleme können polynomzeitlich sein? Turing reduziert sich auf ganzzahlige Faktorisierung?" Oder wollten Sie noch etwas fragen?

Joshua Grochow

Ich bin ein Neuling, also ist meine Frage fast eine Neugier. Alles begann mit einem einfachen Gedanken: Aus der "realen Welt" sehe ich viele NP-vollständige Probleme (ein Postbote, der versucht, seine Kräfte zu schonen, eine Familie, die umzieht und ihre Möbel in einen Lastwagen einbauen möchte, ...: - ))). Aber ich sehe keine "Factoring-Probleme" ... obwohl sie möglicherweise einfacher sind (zwischen P und NPC). ... vielleicht hasst die Realität Multiplikationen :-D :-D

Marzio De Biasi

1

Siehe auch Konsequenzen des Factorings in P?

Jukka Suomela

11

Ich habe keine Antwort auf Ihre Frage, aber ich weiß, dass ein ähnlicher Begriff vor kurzem unter dem Namen "engelbasierte Sicherheit" untersucht wurde.

Der erste Artikel, der dieses Konzept untersucht, ist Prabhakaran & Sahai (STOC '04) . Insbesondere schrieben sie in der Zusammenfassung:

[...] geben wir dem Gegner Zugang zu einer überpolynomialen Rechenleistung.

Ein weiteres wichtiges Papier, das diesen Begriff behandelt, ist das von Canetti, Lin & Pass (FOCS 2010) . Ich habe einige Teile ihrer Konferenzpräsentation gesehen (auf Techtalks ), und wenn ich mich richtig erinnere, beginnen sie mit einem Beispiel, das dem ähnlich ist, was Sie in der Frage erwähnt haben.

MS Dousti
quelle

13

Offensichtlich kann jedes Entscheidungsproblem, das auf Factoring reduziert werden kann, mit einem Factoring-Orakel gelöst werden. Da wir jedoch die Möglichkeit haben, mehrere Abfragen durchzuführen, habe ich versucht, mir ein nicht triviales Problem vorzustellen, für das man mehrere Abfragen durchführen möchte.

Das Problem der Berechnung der Euler-Totientenfunktion scheint ein solches Problem zu sein. Ich weiß nicht, wie ich die Entscheidungsversion dieses Problems durch eine Karp-Reduktion auf die Entscheidungsversion des Factorings lösen soll. Aber mit Turing-Reduzierungen ist es einfach, dies auf Factoring zu reduzieren.

Robin Kothari
quelle

3

Hier ist ein verwandter Artikel in MO über die Komplexität der Berechnung der Totientenfunktion.

Hsien-Chih Chang 張顯之

Kleiner Zusatz: Es gibt auch polynomielle Zeitverkürzungen in die andere Richtung, die Eulers Totientenfunktion berechnen -> Faktorisierung. Ich habe jedoch nicht geprüft, ob die bekannten Reduzierungen für die Entscheidungsversion dieser Probleme funktionieren. Wenn Sie die Totientenfunktion (oder sogar ein festes Vielfaches davon) berechnen können, können Sie dennoch faktorisieren. Shoups Buch widmet sich diesem Thema .

Juan Bermejo Vega

9

Ausarbeitung über Joe frühere Antwort: Beachten Sie, dass . Letzteres ist die zweitniedrigste Klasse in der „niedrigen“ Hierarchie : die also . Dies bedeutet insbesondere , dass Wir können ähnliche Bemerkungen für und $\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}$ Zu zeigen, dass zumindest auf ein grobkörniges Ebene

die gleichen Grenzen wie die Komplexität des Problems hat

selbst, das heißt

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
quelle

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
quelle

5

$\mbox{FNP}$ $P \subseteq P^A \subseteq \Delta_2^p$ $P^{NP}$ $\mbox{BQP}$ $P \subseteq P^A \subseteq P^{NP \cap BQP}$

Joe Fitzsimons
quelle

P mit ganzzahligem Faktorisierungsorakel

Antworten: