Teoría de números: ¿Existe un algoritmo de tiempo polinómico para calcular el enésimo primer o el problema de calcular el enésimo primer es probablemente NP-duro?

Answer 1

NP técnicamente se refiere a problemas de decisión, así que démos una definición formal del problema de decisión NTH-PRIME:

NTH-PRIME (n, X) es verdadero si la enésima prima es igual a X.

¿Es el tamiz de Eratóstenes un algoritmo de tiempo polinómico para este problema de decisión? No, porque la entrada es de tamaño [matemática] \ log_2 n + \ log_2 X \ aprox log_2 n + \ log2 \ pi (n) \ aprox log_2 n + \ log_2 (n \ log n) = 2 \ log_2 n + \ log_2 \ log n [/ math]. Pero, el tamiz lleva tiempo [math] O (n \ log n \ log \ log n) [/ math], que es exponencial en el tamaño de entrada.

Hay métodos más eficientes, consulte Algoritmo más eficiente para enésimo primo, determinista y probabilístico. El método Meissel-Lehmer se ejecuta en el tiempo [math] O (n ^ {2/3}) [/ math]. Pero tenga en cuenta que esto sigue siendo exponencial en el tamaño de entrada [math] \ log_2 n [/ math]. Un artículo de Lagarias y Odlyzko afirma [matemáticas] O (n ^ {1/2}) [/ matemáticas]: Computación π (x): Un método analítico.

¿Es esta formulación del problema incluso en NP? Bueno, un ingenuo “certificado” de que X es el primo [matemático] n [/ matemático] requiere una lista de los primos previos [matemático] n-1 [/ matemático]. Eso ocupa espacio [matemática] O (n \ log n) [/ matemática], que también es exponencial en el tamaño de entrada, al menos en los casos “difíciles”. Meissel-Lehmer te permite hacerlo mejor, pero no lo suficiente para hacer este polinomio, creo. Relajar nuestro problema para requerir [matemáticas] n [/ matemáticas] th prime [matemáticas] \ leq X [/ matemáticas] en cambio no mejora las cosas. La categoría de complejidad adecuada para este problema es en realidad #P (Sharp-P) ya que la respuesta no puede verificarse en tiempo polinómico.

Nadie puede decir definitivamente que NTH-PRIME es * no * en P, por supuesto, pero todas las soluciones más conocidas hoy requieren un tiempo exponencial en la longitud de la entrada (pero sub-lineal en el valor de la entrada).

Para fines prácticos, puede usar una tabla precalculada que lo coloque en el rango correcto, luego tamizar en el rango: consulte El enésimo algoritmo principal Pero esto solo funciona hasta el tamaño máximo de la tabla precalculada.

Answer 2

No existe ningún algoritmo de tiempo polinómico para calcular el enésimo primer.
“La comprobación de la primalidad de un entero se reduce al problema de factorización de enteros”.
Esta afirmación no es verdadera, por favor vea el comentario hecho por Abhimanyu Mongandh Ambalath, que tiene la respuesta,

No se sabe exactamente qué clases de complejidad contienen la versión de decisión del problema de factorización de enteros. Se sabe que está tanto en NP como en co-NP. Esto se debe a que las respuestas SÍ y NO se pueden verificar en tiempo polinómico dados los factores primos (podemos verificar su primalidad utilizando la prueba de primalidad AKS, y que su producto es N por multiplicación).

#Wikipedia

Answer 3

Hay un algoritmo de tiempo polinómico para determinar el enésimo enésimo.

El más simple es el Tamiz de Eratóstenes.

Puede leer el artículo, pero básicamente revisa los números del 2 al N y tacha los compuestos. Es fácil demostrar que la complejidad del tiempo no es peor que O (N ln (N)), que es mejor que O (N ^ 2).

Por otro lado, la cantidad de memoria utilizada podría ser un problema. Si desea el cuadrillonésimo primo, debe almacenar un billón de números, aunque hay formas de evitarlo.

Es importante tener en cuenta que el Tamiz de Eratóstenes no encuentra la enésima prima por factorización, lo que lo haría mucho más difícil de hacer.