# Is prime-counting function #P-complete?

Recall $$\pi(n)$$ the number of primes $$\le n$$ is the prime-counting function. By "PRIMES in P", computing $$\pi(n)$$ is in #P. Is the problem #P-complete? Or, perhaps, there is a complexity reason to believe that this problem is not #P-complete?

P.S. I realize this is a bit naive since somebody must have studied the problem and proved/disproved/conjectured this, but I can't seem to find the answer in the literature. See here if you are curious why I care.

• @MohsenGhorbani: Nope, not the "same" problems. Not even similar. – Igor Pak May 23 '19 at 0:43
• Not evidence against, just curious: do we know a single function $f(n)$ that is #P-complete that really treats n as a number? That is, we can always look at the binary representation of n and treat that binary string as a SAT formula or graph, but I want to avoid that. – Joshua Grochow May 23 '19 at 1:26
• @JoshuaGrochow The "natural" (not NT) hard problems I know with one parameter are all in #EXP-c. An example of such problem: number of tilings of $n \times n$ square with a fixed set $T$ of tiles (i.e. the tiles are not in the input). Thm: there exists $T$ s.t. this problem is #EXP-c. – Igor Pak May 23 '19 at 1:33
• @Joshua This is quite related to NP-completeness of $f(n)$, for which, apparently, we also don't have a definite answer yet: cstheory.stackexchange.com/questions/14124/… – domotorp May 23 '19 at 21:12
• Notice that $\mathrm{\#P^{BPP}=\#P}$, hence $\pi$ was in #P ever since Miller–Rabin. – Emil Jeřábek May 24 '19 at 6:51

Some heuristic evidence: to the best of our knowledge $$\pi(n)$$ looks like a simple function corrected by random fluctuations. Thus I’d expect a poly-time machine with a $$\pi(n)$$ oracle to be no stronger than such a machine with a random oracle, and w.r.t. a random oracle $$X$$ adding a separate random oracle $$Y$$ to $$\mathsf{P}$$ gives $$\#\mathsf{P}^X \not\subset \mathsf{P}^{XY}$$ with probability 1 (here $$Y$$ corresponds to $$\pi(n)$$ and $$X$$ is an independent random oracle).
• I find the last sentence misleading. While indeed $\Pr_X[\mathrm{PP}^X\ne\mathrm{P}^X]=1$, what we actually need here is $\Pr_X[\mathrm{PP}\nsubseteq\mathrm{P}^X]=1$, and we do not know if this is true. In fact, this is equivalent to $\mathrm{PP\ne BPP}$. – Emil Jeřábek May 23 '19 at 15:53
• @EmilJeřábek: Sure, but in terms of evidence that $\pi(n)$ isn't #P-complete, if one could show formally that if it's #P-complete then PP=BPP, I'd take that as pretty strong evidence against #P-completeness... – Joshua Grochow May 23 '19 at 16:02
• @JoshuaGrochow I agree with that. I just don’t think the result on $\mathrm P^X\ne\mathrm{PP}^X$ with random oracle is relevant. – Emil Jeřábek May 23 '19 at 16:07
• @EmilJeřábek: Yep, that’s a good point. Before I edit, would you accept as evidence the fact that $P^{XY} \ne \#P^X$ a.a. given two random oracles, which I think we do know? – Geoffrey Irving May 23 '19 at 17:03