A função de contagem primária é # P-completa?

Lembre-se do número de números primos é a função de contagem primária . Por "PRIMES in P", a computação está em #P. O problema é # P-completo? Ou, talvez, haja um motivo de complexidade para acreditar que esse problema não está # P-completo? $\pi(n)$ $\le n$ $\pi(n)$

PS: Percebo que isso é um pouco ingênuo, pois alguém deve ter estudado o problema e provado / refutado / conjecturado isso, mas não consigo encontrar a resposta na literatura. Veja aqui se você está curioso por que eu me importo.

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

@MohsenGhorbani: Não, não os "mesmos" problemas. Nem parecido.

Igor Pak

Não há evidência contra, apenas curiosa: conhecemos uma única função que é # P-complete que realmente trata n como um número? Ou seja, sempre podemos olhar para a representação binária de n e tratar essa sequência binária como uma fórmula ou gráfico SAT, mas quero evitar isso.

f (n)

$f(n)$

Joshua Grochow

@ JoshuaGrochow Os problemas difíceis "naturais" (não o NT) que conheço com um parâmetro estão todos no # EXP-c. Um exemplo de tal problema: número de pavimentações de quadrado com um conjunto fixo de azulejos (ou seja, os azulejos não são na entrada). Thm: existe st este problema é # EXP-c.

n \times n

$n \times n$

T

$T$

T

$T$

Igor Pak

@ Josué Isso está bastante relacionado à completude NP de , para a qual, aparentemente, também não temos uma resposta definitiva ainda: cstheory.stackexchange.com/questions/14124/…

f (n)

$f(n)$

domotorp

Observe que ; portanto, estava no #P desde Miller-Rabin.

# P^{B P P} = # P

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

π

$\pi$

Emil Jeřábek apoia Monica

Respostas:

Alguma evidência heurística: até onde sabemos parece uma função simples corrigida por flutuações aleatórias. Assim, seria de esperar que uma máquina de tempo com um poli Oracle para ser mais forte do que uma tal máquina com um a Oracle aleatória, e com relação a uma forma aleatória a Oracle adicionando um separado do Oracle aleatório para dá com probabilidade 1 (aqui corresponde a e é um oráculo aleatório independente). $\pi(n)$ $\pi(n)$ $X$ $Y$ $\mathsf{P}$ $\#\mathsf{P}^X \not\subset \mathsf{P}^{XY}$ $Y$ $\pi(n)$ $X$

Geoffrey Irving
fonte

Acho a última frase enganosa. Embora de fato , o que realmente precisamos aqui é , e não sabemos se isso é verdade. De fato, isso é 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 apoia Monica

@ EmilJeřábek: Claro, mas em termos de evidência de que não é # P-completo, se alguém puder mostrar formalmente que se for # P-completo, então PP = BPP, consideraria isso uma evidência bastante forte contra # P-completeness ...

π (n)

$\pi(n)$

Joshua Grochow

@JoshuaGrochow Eu concordo com isso. Só não acho que o resultado em com oracle aleatório seja relevante.

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

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

Emil Jeřábek apoia Monica

@ EmilJeřábek: Sim, esse é um bom ponto. Antes de editar, você aceitaria como evidência o fato de que aa recebeu dois oráculos aleatórios, que eu acho que sabemos?

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

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

Geoffrey Irving

Nós sabemos disso?

Emil Jeřábek apoia Monica