Approximate number of primes below a given integer? 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?
 A: 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 $. 
A: 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
