¿Teoría de la complejidad difícil de verificar el valor de

La función de conteo primo , degradada , se define como el número de números primos menores o iguales que .$\pi(x)$$x$

Podemos definir un problema de decisión desde siguiente manera:$\pi(x)$

Dados dos números y , escritos en binario, decida si .$x$$n$$\pi(x) = n$

Un amigo y yo estábamos hablando sobre este problema hoy temprano. Hay un algoritmo de tiempo pseudopolinomial para este problema: solo cuente hasta , usando la división de prueba en cada paso para ver cuántos números son primos y verifique si es igual a . El problema también está en PSPACE, ya que el algoritmo que acabo de describir se puede implementar para usar solo espacio auxiliar polinómico.$x$$n$

Sin embargo, tengo problemas para encontrar una manera de ubicar este problema en una clase de menor complejidad. No puedo ver cómo construir un verificador de tiempo polinómico para el problema, por lo que no estoy seguro de si está en NP, y no puedo pensar en una forma de llevarlo a la jerarquía polinómica.

¿Cuál es la clase de complejidad más apropiada para este problema?

¡Gracias!

Esto es en gran medida un problema abierto. Dibujaré algunas clases en las que el problema podría encajar "naturalmente".

Es difícil trabajar con su definición, el problema es difícil de encajar en cualquier clase de complejidad existente. El idioma que ha definido es la intersección de los idiomas y { ( x , n ) | K entonces { ( x , n $\{(x,n)|\pi(x)\leq n\}$ . Entonces, por ejemplo, { ( x , n ) | π ( x ) ≤ n } estaba en clase$\{(x,n)|\pi(x)\geq n\}$$\{(x,n)|\pi(x)\leq n\}$$K$ estaría en c o K . Esto hace dar una caracterización de la lengua que ha definido difícil porque uno tendría que Estado "la intersección de una lengua en K con un lenguaje de C o K " para dar el más apretado atado.$\{(x,n)|\pi(x)\geq n\}$$coK$$K$$coK$

El problema "Calcular " es un problema en $\pi(X)$ , donde # P ⊆ F P S P A C E es la clase de problemas de la forma "Calcular el número de rutas de aceptación de un TM polinomial no determinista". Claramente, podemos construir una TM no determinista que adivine un número q ≤ x , y luego (con AKS) comprueba si q es primo.$\#P$$\#P\subseteq FPSPACE$$q \leq x$$q$

Una variante de decisión de es P P , que es la clase de lenguajes que tienen la forma: "Dado un TM polinomial no determinista, ¿aceptan al menos la mitad de las rutas de cálculo?". Ambos { ( x , n ) | π ( x ) ≤ n } y { ( x , n ) | π ( x ) ≥ n } son probablemente reducibles a un problema en P $\#P$$PP$$\{(x,n)|\pi(x)\leq n\}$$\{(x,n)|\pi(x)\geq n\}$$PP$ (haciendo un poco de falsificación de la TM antes mencionada para equilibrar el número de caminos de aceptación).

Tu problema está en C = P$_=$ través del algoritmo$\hspace{-0.06 in}\text{,}$

$\;\;\;$adivinanza no determinista un entero tal que$\big[$m y un poco$\: 0\leq m < 2^{\lceil \hspace{.02 in}\log_{\hspace{.02 in}2}\hspace{-0.02 in}(x+1)\rceil}\big]$b
$\;\;\;$si x < mluego rechazar
$\;\;\;$si b=1entonces:
$\;\;\;\;\;$si m < nluego acepta más rechazar
$\;\;\;$ más:
$\;\;\;\;\;$si m es primo, entonces acepta más rechaza

.


En particular, su problema también está en PP, ya que PP está cerrado bajo reducciones de la tabla de verdad .

En la práctica, puede obtener la respuesta más rápido o más lento :-(

Hay aproximaciones razonablemente buenas para π (x). Entonces calculas tal aproximación, y si está demasiado lejos sabes que π (x) ≠ n. Por ejemplo, si n ≥ x, entonces sé que π (x) ≠ n sin calcular nada.

Hay un algoritmo rápido que determina si π (x) es par o impar, ejecutándose en O (x ^ (1/2)). Puede ejecutar este algoritmo y puede detectar que la paridad de n es incorrecta y ya está. Tiene cincuenta posibilidades si n es un entero aleatorio cercano a π (x).

Aparte de eso, no conozco ningún método que sea más rápido que calcular π (x). Lo cual es muy inconveniente: si escribo un programa que se supone que calcula π (10 ^ 25), y obtengo un resultado que obviamente no es incorrecto, entonces no hay forma de verificar que mi resultado sea correcto, aparte de repetir cálculo. Y no puede simplemente repetir el cálculo usando mi programa, necesita escribir un programa diferente, de lo contrario no detectaría si mi programa tiene algún error que haga que calcule una función ligeramente diferente a π (x).

π (x) se puede calcular razonablemente fácilmente en aproximadamente O (n ^ (2/3)), y más rápido con algunas matemáticas realmente profundas.