¿La función de conteo principal # P-completa?

Recuerde que $\pi(n)$ el número de primos $\le n$ es la función de recuento de primos . Por "PRIMES en P", calcular $\pi(n)$ está en #P. ¿Es el problema # P-completo? O, tal vez, ¿hay una razón compleja para creer que este problema no es # P-completo?

PD: Me doy cuenta de que esto es un poco ingenuo ya que alguien debe haber estudiado el problema y haber probado / refutado / conjeturado esto, pero parece que no puedo encontrar la respuesta en la literatura. Mira aquí si tienes curiosidad por qué me importa.

cc.complexity-theory counting-complexity nt.number-theory comp-number-theory primes Igor Pak
fuente

@MohsenGhorbani: No, no son los "mismos" problemas. Ni siquiera similar.

Igor Pak

No hay evidencia en contra, solo curiosidad: ¿conocemos una sola función

que sea # P-completa que realmente trate a n como un número? Es decir, siempre podemos ver la representación binaria de n y tratar esa cadena binaria como una fórmula o gráfico SAT, pero quiero evitar eso.

f (n)

$f(n)$

Joshua Grochow

@JoshuaGrochow Los problemas difíciles "naturales" (no NT) que conozco con un parámetro están en # EXP-c. Un ejemplo de tal problema: número de inclinaciones de

cuadrado con un conjunto fijo

de mosaicos (es decir, los mosaicos no están en la entrada). Thm: existe

st este problema es # EXP-c.

n \times n

$n \times n$

T

$T$

T

$T$

Igor Pak

@Joshua Esto está bastante relacionado con la integridad de NP de

, para lo cual, aparentemente, tampoco tenemos una respuesta definitiva todavía: cstheory.stackexchange.com/questions/14124/…

f (n)

$f(n)$

domotorp

Observe que

, por lo tanto,

estaba en #P desde Miller – Rabin.

# P^{B P P} = # P

$\mathrm{\#P^{BPP}=\#P}$

π

$\pi$

Emil Jeřábek apoya a Monica

Respuestas:

Alguna evidencia heurística: según nuestro conocimiento, $\pi(n)$ parece una función simple corregida por fluctuaciones aleatorias. Por lo tanto, esperaría que una máquina de poli-tiempo con un oráculo $\pi(n)$ no sea más fuerte que una máquina con un oráculo aleatorio, y wrt un oráculo aleatorio $X$ agregando un oráculo aleatorio separado $Y$ a $\mathsf{P}$ da $\#\mathsf{P}^X \not\subset \mathsf{P}^{XY}$ con probabilidad 1 (aquí $Y$ corresponde a $\pi(n)$ y $X$ es un oráculo aleatorio independiente).

Geoffrey Irving
fuente

La última oración me parece engañosa. Si bien, de hecho,

, lo que realmente necesitamos aquí es

, y no sabemos si esto es cierto. De hecho, esto es equivalente a

\underset{X}{Pr} [{P P}^{X} \neq P^{X}] = 1

$\Pr_X[\mathrm{PP}^X\ne\mathrm{P}^X]=1$

\underset{X}{Pr} [P P ⊈ P^{X}] = 1

$\Pr_X[\mathrm{PP}\nsubseteq\mathrm{P}^X]=1$

P P \neq B P P

$\mathrm{PP\ne BPP}$

Emil Jeřábek apoya a Mónica

@ EmilJeřábek: Claro, pero en términos de evidencia de que

no es # P-completo, si uno pudiera demostrar formalmente que si es # P-completo, entonces PP = BPP, tomaría eso como una evidencia bastante sólida contra # P-completitud ...

π (n)

$\pi(n)$

Joshua Grochow

@JoshuaGrochow Estoy de acuerdo con eso. Simplemente no creo que el resultado en

con oráculo aleatorio sea relevante.

P^{X} \neq {P P}^{X}

$\mathrm P^X\ne\mathrm{PP}^X$

Emil Jeřábek apoya a Mónica

@ EmilJeřábek: Sí, ese es un buen punto. Antes de editar, ¿aceptarías como evidencia el hecho de que

aa da dos oráculos aleatorios, que creo que sí sabemos?

P^{X Y} \neq # P^{X}

$P^{XY} \ne \#P^X$

Geoffrey Irving

¿Sabemos eso?

Emil Jeřábek apoya a Mónica