La fonction de comptage premier # P est-elle complète?

Rappelons le nombre de nombres premiers est la fonction de décompte des nombres premiers . Par "PRIMES in P", le calcul est en #P. Le problème # P-est-il complet? Ou, peut-être, il y a une raison complexe de croire que ce problème n'est pas # P-complet? $\pi(n)$ $\le n$ $\pi(n)$

PS Je me rends compte que c'est un peu naïf car quelqu'un doit avoir étudié le problème et prouvé / réfuté / conjecturé, mais je n'arrive pas à trouver la réponse dans la littérature. Voyez ici si vous êtes curieux de savoir pourquoi je m'en soucie.

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

@MohsenGhorbani: Non, pas les "mêmes" problèmes. Pas même similaire.

Igor Pak

Pas de preuves contre, juste curieux: connaissons-nous une seule fonction qui est # P-complète qui traite vraiment n comme un nombre? Autrement dit, nous pouvons toujours regarder la représentation binaire de n et traiter cette chaîne binaire comme une formule SAT ou un graphique, mais je veux éviter cela.

f (n)

$f(n)$

Joshua Grochow

@JoshuaGrochow Les problèmes difficiles "naturels" (pas NT) que je connais avec un paramètre sont tous dans # EXP-c. Un exemple d' un tel problème: le nombre de pavages de carré avec un ensemble fixe de carreaux ( à savoir les tuiles ne sont pas dans l'entrée). Thm: il existe st ce problème est # EXP-c.

n \times n

$n \times n$

T

$T$

T

$T$

Igor Pak

@Joshua Ceci est tout à fait lié à l'exhaustivité de NP de

f (n)

$f(n)$ , pour lequel, apparemment, nous n'avons pas encore de réponse définitive: cstheory.stackexchange.com/questions/14124/…

domotorp

Notez que

# P^{B P P} = # P

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

π

$\pi$ était dans #P depuis Miller – Rabin.

Emil Jeřábek soutient Monica

Réponses:

$\pi(n)$ $\pi(n)$ $X$ $Y$ $\mathsf{P}$ $\#\mathsf{P}^X \not\subset \mathsf{P}^{XY}$ $Y$ $\pi(n)$ $X$

Geoffrey Irving
la source

Je trouve la dernière phrase trompeuse. Alors effet , ce dont nous avons réellement besoin ici est , et nous ne savons pas si cela est vrai. En fait, cela équivaut à .

\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 soutient Monica

@ EmilJeřábek: Bien sûr, mais en termes de preuves que n'est pas # P-complet, si l'on pouvait montrer formellement que si c'est # P-complet alors PP = BPP, je prendrais cela comme une preuve assez forte contre # P-exhausteness ...

π (n)

$\pi(n)$

Joshua Grochow

@JoshuaGrochow Je suis d'accord avec cela. Je ne pense pas que le résultat sur avec oracle aléatoire soit pertinent.

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

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

Emil Jeřábek soutient Monica

@ EmilJeřábek: Oui, c'est un bon point. Avant d'éditer, accepteriez-vous comme preuve le fait que aa donné deux oracles aléatoires, que je pense que nous connaissons?

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

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

Geoffrey Irving

Le savons-nous?

Emil Jeřábek soutient Monica