¿Se sabe que los problemas PRIMES, FACTORING son P-hard?

Deje que PRIMES (también conocido como prueba de primalidad ) sea el problema:

Dado un número natural $n$ , ¿es $n$ un número primo?

Deje que FACTORING sea el problema:

Dados los números naturales , con , ¿ tiene un factor con ? $n$ $m$ $1 \leq m \leq n$ $n$ $d$ $1 < d < m$

¿Se sabe si PRIMES es P-duro? ¿Qué tal FACTORING? ¿Cuáles son los límites inferiores más conocidos para estos problemas?

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

No, IIRC está abierto si Primes es P-hard. Creo que lo mismo es cierto sobre FACTORING.

Kaveh

Supongo que una pregunta alternativa podría ser: ¿hay alguna consecuencia de que PRIMES o FACTORING sean P-hard?

Suresh Venkat

@Suresh: esa es una buena pregunta. ¿Podrías publicarlo por separado?

András Salamon

En realidad, ya se le ha pedido factorizar: cstheory.stackexchange.com/questions/5096/…

Suresh Venkat

@ Arte, estoy de acuerdo con András, una pregunta sobre las consecuencias de la dureza P de Primes sería interesante. También edité la pregunta agregando una pregunta sobre los límites inferiores más conocidos.

Kaveh

Respuestas:

Se sabe que PRIMES es difícil para . Vea mi artículo con Saks y Shparlinski, " A Lower Bound for Primality " en JCSS 62 (2001). Ninguna mejora en ese frente desde entonces. $\mathsf{TC^0}$

Eric Allender
fuente

¿Sabes si este resultado de dureza también se cumple si solo queremos algo aleatorio

de todos losenteros de

bits que se deben factorizar? Después de todo esto todavía podría estar en

¿verdad?

\frac{1}{n}

$\frac1 n$

n

$n$

A C C^{0}

$ACC^0$

T ....

La factorización se puede lograr mediante el uso de un circuito cuántico de profundidad polylog y el procesamiento previo y posterior de ZPP; Mira este artículo . Si fuera P-hard, cualquier algoritmo en P podría hacerse con un circuito cuántico de profundidad polylog y los mismos pasos de pre y postprocesamiento. Creo que estos pasos son exponenciación modular y fracciones continuas, lo que para mí parece poco probable que sea lo suficientemente potente como para resolver problemas P-completos, incluso con la adición de un circuito cuántico de profundidad polylog . $n$ $n$ $n$

Peter Shor
fuente