Sind die Probleme PRIMES, FACTORING als P-hart bekannt?

Lass PRIMES (aka Primality Testing ) das Problem sein:

Gegeben eine natürliche Zahl , ist eine Primzahl? $n$ $n$

Lass FACTORING das Problem sein:

In Anbetracht natürliche Zahlen , mit , ist einen Faktor mit ? $n$ $m$ $1 \leq m \leq n$ $n$ $d$ $1 < d < m$

Ist bekannt, ob PRIMES P-hart ist? Wie wäre es mit FACTORING? Was sind die bekanntesten unteren Grenzen für diese Probleme?

cc.complexity-theory lower-bounds factoring primes p-hardness km
quelle

Nein, IIRC ist offen, wenn Primes P-schwer ist. Ich denke, dasselbe gilt für FACTORING.

Kaveh

Ich denke, eine andere Frage könnte sein: Gibt es irgendwelche Konsequenzen dafür, dass PRIMES oder FACTORING P-hard sind?

Suresh Venkat

@Suresh: das ist eine schöne frage. Könnten Sie es separat posten?

András Salamon

Eigentlich wurde schon nach Factoring gefragt: cstheory.stackexchange.com/questions/5096/…

Suresh Venkat

@Artem, da stimme ich András zu, wäre eine Frage zu den Folgen der P-Härte von Primes interessant. Ich habe die Frage auch bearbeitet, indem ich eine Frage zu den bekanntesten Lowerbounds hinzugefügt habe.

Kaveh

Antworten:

PRIMES ist dafür bekannt, dass es für . Siehe meine Arbeit mit Saks und Shparlinski, " A Lower Bound for Primality " in JCSS 62 (2001). Seitdem keine Verbesserung in dieser Hinsicht. $\mathsf{TC^0}$

Eric Allender
quelle

Wissen Sie, ob dieses Härteergebnis auch gilt, wenn nur einige zufällige aller Bit-Ganzzahlen berücksichtigt werden sollen? Könnte das doch noch in oder?

\frac{1}{n}

$\frac1 n$

n

$n$

A C C^{0}

$ACC^0$

T ....

Das Faktorisieren kann unter Verwendung einer Polylog- Tiefen-Quantenschaltung und einer ZPP-Vor- und Nachbearbeitung erreicht werden; siehe dieses Papier . Wenn es P-schwer wäre, könnte jeder Algorithmus in P mit einer Polylog- Tiefen-Quantenschaltung und den gleichen Vor- und Nachverarbeitungsschritten durchgeführt werden. Ich glaube, diese Schritte sind modulare Exponentiation und fortgesetzte Brüche, die für die Lösung von P-vollständigen Problemen wahrscheinlich nicht leistungsfähig genug sind, selbst wenn eine Quantenschaltung mit einer Tiefe von Polylog hinzugefügt wird . $n$ $n$ $n$

Peter Shor
quelle