6
$\begingroup$

The problem of the complexity of the exact counting problem for primes is interesting. The best result we have about primes is that it is hard for TC0. But counting the number of witnesses to a TC0 function can be as difficult as sharpP. The best upper-bound is P by AKS which gives a sharpP upper-bound for the exact counting problem.

There is no known algorithm for exact counting better that P, otherwise we would be able to check if a number x is a prime by counting the number of primes before x-1 and x and comparing them.

The problem can't be in P unless we can solve the problem of finding prime numbers in P which is an open problem: we can use a binary search to find the first prime number after x by finding the first number y>x where there are more primes before y than x.

Can we do better if we relax the question to approximate counting? I know that the question is not completely well-defined. We need to first clarify what we mean by "approximate", e.g., an absolute error or a relative error? etc. But I don't know what would be a good definition.

Given $n$, how well can we approximate the number of prime numbers below $n$ in polynomial time?

Improve this question
$\endgroup$
6
  • 3
    $\begingroup$ Any particular reason you put [closed] at the end of your own question? I'm guessing you thought people wouldn't look at it then, and it'd stay open? (See tea.mathoverflow.net/discussion/1543) $\endgroup$
    – Zev Chonoles
    Commented Apr 8, 2013 at 0:52
  • 6
    $\begingroup$ This is all more strange because the questions seems to make sense, and to be of some interest. $\endgroup$
    – Joël
    Commented Apr 8, 2013 at 0:57
  • 3
    $\begingroup$ The obvious upper bound, assuming RH, is $O(\sqrt{x} \ln x)$, using $Li(x)$. $\endgroup$
    – Will Sawin
    Commented Apr 8, 2013 at 1:32
  • 6
    $\begingroup$ For example, how would one prove that there is no algorithm computing the number $\pi(n)$ of primes up to $n$ in polynomial time ? Or is it not possible to prove statements like this with current technology ? Is it even true ? After all, in Hardy's book "Ramanujan", Hardy mentions several false formulas that the young Ramanujan believed to have proved expressing $\pi(x)$ as the sum of a series, and such a formula would give, if I am not mistaken, such an algorithm. The formulas happened to be false, but is there a reason such formulas cannot be true ? $\endgroup$
    – Joël
    Commented Apr 8, 2013 at 3:58
  • $\begingroup$ @Joël, of course you are right. I would, however, like to see some evidence that the person asking knows what all the words mean. $\endgroup$
    – Will Jagy
    Commented Apr 8, 2013 at 4:54

2 Answers 2

Reset to default
10
$\begingroup$

The Lagarias-Odlyzko algorithm gives a method for counting the number of primes less than $n$ in time $O_{\epsilon} ( n^{1/2+\epsilon})$ time. Roughly speaking, this algorithm proceeds by expressing the prime counting function as an integral involving the Riemann zeta function and then approximating the integral with numerical integration. This is currently the best known result in this direction, however the Polymath4 project found an algorithm for computing the parity of the number of primes less than $n$ in time $n^{1/2 -\delta}$ for some small $\delta > 0 $.

Improve this answer
$\endgroup$
4
  • 4
    $\begingroup$ I'm guessing the words "polynomial time" above are meant in the logarithm of $n$. To answer that, it would be interesting to know how well the Lagarias-Odlyzko algorithm approximates $\pi(x)$ if one is only willing to put it in $log^k(x)$ time. $\endgroup$
    – Dror Speiser
    Commented Apr 8, 2013 at 7:57
  • $\begingroup$ So we have subexponential time algorithm, but nothing close to a polynomial time. Is it expected that there is no polynomial time algorithm, or on the contrary that there is some method ? Or perhaps people disagree about what to expect, as I have read somewhere on this site, they disagree if we ought to expect that the factorization problem can be solved in polynomial time or not. An indication that there might be a positive answer is an analogy with an admittedly rather different case, the one of the partition function $p(n)$. Computing it naively is certainly exponential time (or more)... $\endgroup$
    – Joël
    Commented Apr 8, 2013 at 13:53
  • $\begingroup$ but the formula of Hardy, Ramanujan and Rademacher allows for an exact computation in polynomial time. $\endgroup$
    – Joël
    Commented Apr 8, 2013 at 13:55
  • 1
    $\begingroup$ @Dror, I agree that that is likely what Alex meant. I didn't mean to suggest that this was a complete solution, only partial progress. $\endgroup$
    – Mark Lewko
    Commented Apr 8, 2013 at 21:34
0
$\begingroup$

The problem of the complexity of the exact counting problem for primes is interesting. The best result we have about primes is that it is hard for TC0. But counting the number of witnesses to a TC0 function can be as difficult as sharpP. The best upper-bound is P by AKS which gives a sharpP upper-bound for the exact counting problem.

There is no known algorithm for exact counting better that P, otherwise we would be able to check if a number x is a prime by counting the number of primes before x-1 and x and comparing them. The problem can't be in P unless we can solve the problem of finding prime numbers in P which is an open problem: we can use a binary search to find the first prime number after x by finding the first number y>x where there are more primes before y than x.

Can we do better if we relax the question to approximate counting? I know that the question is not completely well-defined. We need to first clarify what we mean by "approximate", e.g., an absolute error or a relative error? etc. But I don't know what would be a good definition.

PS I added [closed] to the title. I wanted to test if anyone reads closed questions. No mischief was intended.

Alex

Improve this answer
$\endgroup$
8
  • 2
    $\begingroup$ Turning this around, it is not known that P$\neq$#P, so there is no way to show that one cannot get perfect accuracy in polynomial time. $\endgroup$
    – Will Sawin
    Commented Apr 8, 2013 at 7:01
  • $\begingroup$ To Alex: I think some dark side of the human soul makes that people are even more likely to read a question if it is closed, somewhat similarly to the well-known phenomenon as people driving much slower on the highway when there has been a car accident on the other side, just to have more time to look at what happened. $\endgroup$
    – Joël
    Commented Apr 8, 2013 at 13:48
  • 1
    $\begingroup$ Alex, so if I understand well, one can formulate your question in a more open-ended way as follows: given $\epsilon>0$, what is the time $T_a(n,\epsilon)$ (resp $T_r(n,\epsilon)$) that the best known algorithm takes to compute $\pi(n)$ with an error less than $\epsilon$ (resp. less than $\epsilon \pi(n)$)? Also one can replace best known algorithm with best possible algorithm, so that makes four question. Are you more interested into what one can do right now, or what is eventually possible? The answer depends on two variables, so may be more subtle than a dichotomy polynomial/exponential. $\endgroup$
    – Joël
    Commented Apr 8, 2013 at 14:05
  • 2
    $\begingroup$ @Alex, I noticed you set up a separate account (with the same name) for your answer here. You might look into getting the two accounts merged. (You really should have edited the original question instead of posting an answer.) $\endgroup$
    – Barry Cipra
    Commented Apr 8, 2013 at 14:37
  • 1
    $\begingroup$ @Joël, unregistered users cannot edit their own posts: there is no way to log into an unregistered account. The software uses a temporary cookie in the browser to remember unregistered users, however as soon as the cookie is deleted the user looses access to the account. $\endgroup$
    – Kaveh
    Commented Apr 10, 2013 at 20:20

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .