Si la conjetura de Goldbach es verdadera, entonces dado un número par [matemática] e [/ matemática], ¿cuál es la complejidad de encontrar números primos [matemática] p_1 [/ matemática] y [matemática] p_2 [/ matemática] tal que [matemática] p_1 + p_2 = e [/ matemáticas]?

Answer 1

Eso depende de la “manera” en que el GC es verdadero. Solo saber que es cierto no es suficiente para precisar la complejidad de encontrar un par de números primos para un entero par dado.

Por ejemplo, es teóricamente posible que GC sea verdadero “apenas”, lo que significa que para infinitos números pares (o, mejor, para un conjunto denso de números pares), solo hay un par de primos que suman número. En este caso, es concebible que encontrar esa aguja en un pajar sea tan difícil como factorizar una cantidad de tamaño comparable.

Sin embargo, esto no es absolutamente lo que esperamos. Lo que esperamos es que para todos los números pares, hay toneladas y toneladas de pares de números primos adecuados. De hecho, sospechamos que por cada p menor que n (para n par), la probabilidad de que np sea primo es exactamente la misma que la de cualquier número de tamaño comparable.

Si eso es así, la complejidad (aleatoria) de encontrar un par primo es significativamente menor que la factorización. Simplemente pruebe pequeños números primos en secuencia hasta que la diferencia también sea primo; esto no debería tomar más que un número logarítmico de intentos, por lo que la complejidad es polinomial (en el número de dígitos, que es cómo se calculan estas cosas) en lugar de superpolinomial (como sospechamos que es la factorización).

Answer 2

El método de fuerza bruta sería verificar si [math] ep [/ math] es primo para todos los primos [math] p \ le \ frac {e} {2} [/ math].

La generación de la lista de primos hasta [matemática] \ frac {e} {2} [/ matemática] se puede hacer en [matemática] O \ left (\ frac {e} {\ log (\ log e)} \ right) [/ math] usando el Tamiz de Atkin.

La prueba de si [math] ep [/ math] es primo se puede hacer en [math] O \ left ((\ log e) ^ {6+ \ epsilon} \ right) [/ math] utilizando la prueba de primalidad AKS.

Según el Teorema de los números primos, habrá [matemáticas] O \ izquierda (\ dfrac {e} {\ log e} \ derecha) [/ matemáticas] números primos [matemáticas] p [/ matemáticas] en la lista. Entonces, probar si [math] ep [/ math] es primo para todos estos primos [math] p [/ math] tomará como máximo [math] O \ left (e (\ log e) ^ {5+ \ epsilon } \ right) [/ math]

Entonces, el tiempo de ejecución general que usa este algoritmo es [matemática] O \ left (e (\ log e) ^ {5+ \ epsilon} \ right) [/ math].

Por supuesto, puede haber una forma más rápida.

Answer 3

El análisis dado por Santhosh Karnik se basa en el uso del Tamiz de Atkin para producir iterativamente números primos menores que [math] e / 2 [/ math] y dentro de ese ciclo probar la primalidad de [math] ep [/ math], donde [ math] p [/ math] es el número primo generado.

La respuesta de Alon Amit es mejor. Aquí hay una explicación diferente de su respuesta.

Si uno adopta el enfoque de generar todos los números primos menores que [math] e [/ math] y almacenarlos en una matriz, la complejidad de encontrar todos los pares que satisfagan el problema es [math] O (e) [/ math].

Un esquema del algoritmo es el siguiente:

1. Genere la matriz ordenada de primos menores que [math] e [/ math]. Esto tiene complejidad [matemática] O \ left ({e \ over \ log (\ log (e))} \ right) [/ math] usando el Tamiz de Atkin. Según el teorema del número primo, la matriz así producida tiene una longitud que se aproxima asintóticamente a [math] n = e / \ log (e) [/ math].

2. Busque [math] e / 2 [/ math] en la matriz. Usando una búsqueda binaria, esto tiene una complejidad computacional de [math] O (\ log (n)) [/ math]. Si [math] e / 2 [/ math] está en la matriz, envíe el par [math] (e / 2, e / 2) [/ math] como una de las soluciones.

3. Un subproducto del paso 2 produce un índice en la matriz que se puede usar para dividirlo en primos menores que [math] e / 2 [/ math] y primos mayores que [math] e / 2 [/ math]. Para cualquier valor de [math] e [/ math] en este paso, la lista de números mayores que [math] e / 2 [/ math] tendrá una longitud no mayor que [math] n / 2 [/ math]. [De hecho, una consecuencia del teorema del número primo es que si [math] e [/ math] es al menos 12, entonces la partición de primos mayor que [math] e / 2 [/ math] tendrá menos elementos que la partición de primos más pequeños.]

4. Para cada número primo [math] p [/ math] en la partición de números más grandes, use una búsqueda binaria para determinar si [math] ep [/ math] está en la matriz. Si [math] ep [/ math] está en la matriz, envíe el par [math] (ep, p) [/ math] como una de las soluciones.

Al final del paso 4, obtendrá una lista de pares que suman [math] e [/ math]. La lista estará vacía en el improbable caso de que la conjetura de Goldbach falle para [math] e [/ math]. La complejidad computacional del paso 4 es [matemática] O (n \ log (n)) [/ matemática]. Sustituyendo [math] e / \ log (e) [/ math] por [math] n [/ math] y eliminando los términos dominados por otros se obtiene [math] O (e) [/ math]. Dado que la complejidad del paso 4 domina la complejidad del paso 1, la complejidad computacional general de este enfoque es [matemática] O (e) [/ matemática].