<p>Some heuristic evidence: to the best of our knowledge  <span class="math-container">$\pi(n)$</span> looks like a simple function corrected by random fluctuations.  Thus I’d expect a poly-time machine with a <span class="math-container">$\pi(n)$</span> oracle to be no stronger than such a machine with a random oracle, and w.r.t. a random oracle <span class="math-container">$X$</span> adding a separate random oracle <span class="math-container">$Y$</span> to <span class="math-container">$\mathsf{P}$</span> gives <span class="math-container">$\#\mathsf{P}^X \not\subset \mathsf{P}^{XY}$</span> with probability 1 (here <span class="math-container">$Y$</span> corresponds to <span class="math-container">$\pi(n)$</span> and <span class="math-container">$X$</span> is an independent random oracle).</p>

CC BY-SA 4.0
2019-05-23T15:53:57.933Z
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
CC BY-SA 4.0
2019-05-23T16:02:52.983Z
@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
CC BY-SA 4.0
2019-05-23T16:07:33.440Z
@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
CC BY-SA 4.0
2019-05-23T17:03:44.913Z
@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
CC BY-SA 4.0
2019-05-23T17:24:00.137Z
Do we know that?
Emil Jeřábek
CC BY-SA 4.0
2019-05-23T17:35:42.527Z
We know that $\mathsf{BPP} < \mathsf{NP}$ w.r.t. a random oracle (according to https://en.wikipedia.org/wiki/BPP_(complexity)), and presumably the same proof gives $\mathsf{P}^{XY} \ne \mathsf{NP}^X$.
Geoffrey Irving
CC BY-SA 4.0
2019-05-23T15:33:25.320Z
2019-05-23T17:43:21.943Z
2019-05-23T17:43:21.943Z
Geoffrey Irving
<p>Recall <span class="math-container">$\pi(n)$</span> the number of primes <span class="math-container">$\le n$</span> is the <a href="https://en.wikipedia.org/wiki/Prime-counting_function" rel="noreferrer">prime-counting function</a>.  By "PRIMES in P", computing <span class="math-container">$\pi(n)$</span> 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>

<p>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 <a href="http://www.math.ucla.edu/~pak/papers/ICM-paper9.pdf" rel="noreferrer">here</a> if you are curious why I care. </p>

CC BY-SA 4.0
2019-05-23T00:39:18.903Z
I think a BQP algorithm may solve this problem. we know how to factoring a number with a BQP‌ algorithm and I think these problems are same but I don't know how to reducing this problem to factoring at these moment!(it is just a gues) #P-Complete is a very large complexity class and It is unlikely that BQP  to have #P-Complete problems.
Mohsen Ghorbani
CC BY-SA 4.0
2019-05-23T00:43:50.237Z
@MohsenGhorbani: Nope, not the "same" problems.  Not even similar.
Igor Pak
CC BY-SA 4.0
2019-05-23T01:26:09.010Z
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
CC BY-SA 4.0
2019-05-23T01:33:21.373Z
@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
CC BY-SA 4.0
2019-05-23T21:12:10.630Z
@Joshua This is quite related to NP-completeness of $f(n)$, for which, apparently, we also don't have a definite answer yet: https://cstheory.stackexchange.com/questions/14124/is-there-a-natural-problem-on-the-naturals-that-is-np-complete
domotorp
CC BY-SA 4.0
2019-05-24T06:51:53.573Z
Notice that $\mathrm{\#P^{BPP}=\#P}$, hence $\pi$ was in #P ever since Miller–Rabin.
Emil Jeřábek
CC BY-SA 4.0
2019-05-24T06:57:00.063Z
@EmilJeřábek:  I did not know that.  Is this a standard textbook result?
Igor Pak
CC BY-SA 4.0
2019-05-24T07:33:02.437Z
Yes, this is a standard result. It comes from Köbler, Schöning, Toda & Torán, "Turing machines with few accepting computations and low sets for PP".
Emil Jeřábek
CC BY-SA 4.0
2019-05-24T08:44:17.507Z
Sorry, what I wrote is not quite correct. It’s true that $\mathrm{PP^{BPP}=PP}$, but for #P, we only get a reduction: if $f\in\#\mathrm{P^{BPP}}$, there is $g\in\#\mathrm P$ and a polynomial $p$ such that $f(w)=\lfloor g(w)2^{-p(|w|)}\rfloor$ ($|w|$ being the length of the input $w$).
Emil Jeřábek
<cc.complexity-theory><counting-complexity><nt.number-theory><comp-number-theory><primes>
Is prime-counting function #P-complete?
Igor Pak
# Is prime-counting function #P-complete?

(Asked by: username_0 on 2019-05-22)

Recall $\pi(n)$ the number of primes $\le n$ is the [prime-counting function](https://en.wikipedia.org/wiki/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](http://www.math.ucla.edu/~pak/papers/ICM-paper9.pdf) if you are curious why I care.

**Tags:** cc.complexity-theory, counting-complexity, nt.number-theory, comp-number-theory, primes
> **Comments:**
> **username_1**: I think a BQP algorithm may solve this problem. we know how to factoring a number with a BQP‌ algorithm and I think these problems are same but I don't know how to reducing this problem to factoring at these moment!(it is just a gues) #P-Complete is a very large complexity class and It is unlikely that BQP  to have #P-Complete problems.  
> **username_0**: @MohsenGhorbani: Nope, not the "same" problems.  Not even similar.  
> **username_2**: 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.  
> **username_0**: @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.  
> **username_3**: @Joshua This is quite related to NP-completeness of $f(n)$, for which, apparently, we also don't have a definite answer yet: https://cstheory.stackexchange.com/questions/14124/is-there-a-natural-problem-on-the-naturals-that-is-np-complete  
> **username_4**: Notice that $\mathrm{\#P^{BPP}=\#P}$, hence $\pi$ was in #P ever since Miller–Rabin.  
> **username_0**: @EmilJeřábek:  I did not know that.  Is this a standard textbook result?  
> **username_4**: Yes, this is a standard result. It comes from Köbler, Schöning, Toda & Torán, "Turing machines with few accepting computations and low sets for PP".  
> **username_4**: Sorry, what I wrote is not quite correct. It’s true that $\mathrm{PP^{BPP}=PP}$, but for #P, we only get a reduction: if $f\in\#\mathrm{P^{BPP}}$, there is $g\in\#\mathrm P$ and a polynomial $p$ such that $f(w)=\lfloor g(w)2^{-p(|w|)}\rfloor$ ($|w|$ being the length of the input $w$).  

---

## 1 answers

### Answer by username_5 on 2019-05-23. Score: 2

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).

> **Comments:**
> **username_4**: 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}$.  
> **username_2**: @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...  
> **username_4**: @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.  
> **username_5**: @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?  
> **username_4**: Do we know that?  
> **username_5**: We know that $\mathsf{BPP} < \mathsf{NP}$ w.r.t. a random oracle (according to https://en.wikipedia.org/wiki/BPP_(complexity)), and presumably the same proof gives $\mathsf{P}^{XY} \ne \mathsf{NP}^X$.  

---

