The prime-counting function, demoted $\pi(x)$, is defined as the number of prime numbers less than or equal to $x$.
We can define a decision problem from $\pi(x)$ as follows:
Given two numbers $x$ and $n$, written in binary, decide if $\pi(x) = n$.
A friend and I were talking about this problem earlier today. There's a pseudopolynomial-time algorithm for this problem - just count up to $x$, using trial division at each step to see how many of the numbers are prime, and check if that's equal to $n$. The problem is also in PSPACE, since the algorithm I just described can be implemented to use only polynomial auxiliary space.
However, I'm having trouble finding a way to place this problem into a lower complexity class. I can't see how to build a polynomial-time verifier for the problem, so I'm not sure whether it's in NP, and I can't think of a way to get it into the polynomial hierarchy at all.
What is the most appropriate complexity class for this problem?
Thanks!