20

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.

Igor Pak
  • 812
  • 5
  • 15
  • 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 May 23 '19 at 00:39
  • 5
    @MohsenGhorbani: Nope, not the "same" problems. Not even similar. – Igor Pak May 23 '19 at 00:43
  • 4
    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 01:26
  • 3
    @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 01:33
  • 1
    @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 May 23 '19 at 21:12
  • 2
    Notice that $\mathrm{#P^{BPP}=#P}$, hence $\pi$ was in #P ever since Miller–Rabin. – Emil Jeřábek May 24 '19 at 06:51
  • @EmilJeřábek: I did not know that. Is this a standard textbook result? – Igor Pak May 24 '19 at 06:57
  • 1
    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 May 24 '19 at 07:33
  • 1
    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 May 24 '19 at 08:44

1 Answers1

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

Geoffrey Irving
  • 3,253
  • 15
  • 29
  • 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}$. – Emil Jeřábek May 23 '19 at 15:53
  • 1
    @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
  • 3
    @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
  • 1
    @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
  • 1
    Do we know that? – Emil Jeřábek May 23 '19 at 17:24
  • 1
    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 May 23 '19 at 17:35