20
$\begingroup$

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.

$\endgroup$
  • 5
    $\begingroup$ @MohsenGhorbani: Nope, not the "same" problems. Not even similar. $\endgroup$ – Igor Pak May 23 at 0:43
  • 4
    $\begingroup$ 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. $\endgroup$ – Joshua Grochow May 23 at 1:26
  • 3
    $\begingroup$ @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. $\endgroup$ – Igor Pak May 23 at 1:33
  • 1
    $\begingroup$ @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/… $\endgroup$ – domotorp May 23 at 21:12
  • 2
    $\begingroup$ Notice that $\mathrm{\#P^{BPP}=\#P}$, hence $\pi$ was in #P ever since Miller–Rabin. $\endgroup$ – Emil Jeřábek supports Monica May 24 at 6:51
2
$\begingroup$

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

$\endgroup$
  • 4
    $\begingroup$ 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}$. $\endgroup$ – Emil Jeřábek supports Monica May 23 at 15:53
  • 1
    $\begingroup$ @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... $\endgroup$ – Joshua Grochow May 23 at 16:02
  • 3
    $\begingroup$ @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. $\endgroup$ – Emil Jeřábek supports Monica May 23 at 16:07
  • 1
    $\begingroup$ @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? $\endgroup$ – Geoffrey Irving May 23 at 17:03
  • 1
    $\begingroup$ Do we know that? $\endgroup$ – Emil Jeřábek supports Monica May 23 at 17:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.