¿Qué es la complejidad computacional de cálculo de $\pi(x)$ exactamente?

Question

La primer función de recuento $\pi(x)$ se ha determinado para $x=10^{26}$.

La lista de las $10^n$-ésimo de los números primos , sin embargo , termina en $n=18$. El $10^{18}$-th prime ha $20$ dígitos.

Apparantly, la determinación del $\pi(x)$ es más fácil que la determinación del $p_n$ ($n$- ésimo primo).

¿Qué es la complejidad computacional de determinar el $\pi(n)$ exactamente ?

¿Qué es la complejidad computacional de la determinación de la $n$-ésimo primo ?

Es el segundo problema más difícil que el primero ? (Creo que este no es el caso porque con búsqueda binaria, debe ser posible determinar el $p_n$ casi tan eficiente como la determinación de $\pi(n)$)

Es cierto que el problema no es de gran interés práctico debido a $li(x)$ es una muy buena aproximación de la $\pi(x)$. Yo estoy solo por curiosidad, en qué medida el cálculo exacto podría continuar con la actual potencia de cálculo disponible.

Answer 1

Ahora mismo hay dos competidores métodos para determinar el $\pi(x)$ al $x$ es grande: la combinatoria método de Meissel-Lehmer-Lagarias-Miller-Odlyzko-Deleglise-Rivat (ver aquí), que exige $O(\frac{x^{\frac{2}{3}}}{(\log x)^2})$ tiempo y $O(x^{\frac{1}{3}}(\log x)^2)$ espacio, y el método analítico de Lagarias-Odlyzko (ver aquí), que exige $O(x^{\frac{1}{2}+\epsilon})$ tiempo y $O(x^{\frac{1}{4}+\epsilon})$ espacio. (Aunque en realidad, el último método puede ser modificado para exigir $O(x^{\frac{3-2\delta}{5}+\epsilon})$ tiempo y $O(x^{\delta+\epsilon})$ espacio para $0 \le \delta \le \frac{1}{4}$.)

Curiosamente, el registro de $\pi(10^{26})$ se obtuvo utilizando el método combinatorio, que es más lento asintóticamente; tal vez el punto de cruce no ha sido alcanzado aún. Otro factor es probable que la dificultad de la implementación del método analítico.

Como dices, se puede utilizar $\pi(n)$ para determinar el $p_n$, y la complejidad computacional no será muy diferente asintóticamente; sin embargo, la diferencia es probablemente suficiente para provocar $p_n$ a la zaga, ya que sería necesario para evaluar $\pi(n)$ muchas veces sólo para determinar un valor de $p_n$. Pero, yo diría que la diferencia de un factor de $10^6$ entre los dos registros es probablemente debido a la menor atención a $p_n$.