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.

Improve this question
$\endgroup$
9
  • 5
    $\begingroup$ @MohsenGhorbani: Nope, not the "same" problems. Not even similar. $\endgroup$
    – Igor Pak
    May 23, 2019 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, 2019 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, 2019 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, 2019 at 21:12
  • 2
    $\begingroup$ Notice that $\mathrm{\#P^{BPP}=\#P}$, hence $\pi$ was in #P ever since Miller–Rabin. $\endgroup$
    – Emil Jeřábek
    May 24, 2019 at 6:51

1 Answer 1

Reset to default
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).

Improve this answer
$\endgroup$
6
  • 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
    May 23, 2019 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, 2019 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
    May 23, 2019 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, 2019 at 17:03
  • 1
    $\begingroup$ Do we know that? $\endgroup$
    – Emil Jeřábek
    May 23, 2019 at 17:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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