Complexity-theoretic difficult of checking the value of $\pi(x)$?

Question

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!

Answer 1

This is very much an open problem. I'll sketch some classes that the problem could "naturally" fit in.

Your definition is somewhat awkward to work with, the problem is hard to fit in to any existing complexity class. The language you've defined is the intersection of the languages $\{(x,n)|\pi(x)\leq n\}$ and $\{(x,n)|\pi(x)\geq n\}$. So if for instance $\{(x,n)|\pi(x)\leq n\}$ was in class $K$ then $\{(x,n)|\pi(x)\geq n\}$ would be in $coK$. This makes giving a characterization of the language you've defined hard because one would have to state "the intersection of a language in $K$ with a language in $coK$" to give the tightest bound.

The problem "Compute $\pi(X)$" is a problem in $\#P$, where $\#P\subseteq FPSPACE$ is the class of problems of the form "Compute the number of accepting paths of a nondeterministic, polynomial TM". Clearly we can construct a nondeterministic TM that guesses a number $q \leq x$, and then (with AKS) tests whether $q$ is prime.

A decision variant of $\#P$ is $PP$, which is the class of languages that are of the form: "Given a nondeterministic polynomial TM, do at least half the computation paths accept?". Both $\{(x,n)|\pi(x)\leq n\}$ and $\{(x,n)|\pi(x)\geq n\}$ are probably reducible to a problem in $PP$ (by doing some fudging to the aforementioned TM to balance out the number of accepting paths).

Answer 2

Your problem is in C$_=$P $\hspace{-0.06 in}\text{,}$ via the algorithm

$\;\;\;$ non-deterministically guess $\big[$an integer m such that $\: 0\leq m < 2^{\lceil \hspace{.02 in}\log_{\hspace{.02 in}2}\hspace{-0.02 in}(x+1)\rceil}\big]$ and a bit b
$\;\;\;$ if x < m then reject
$\;\;\;$ if b=1 then:
$\;\;\;\;\;$ if m < n then accept else reject
$\;\;\;$ else:
$\;\;\;\;\;$ if m is prime then accept else reject

.


In particular, your problem is also in PP, since PP is closed under truth-table reductions.

Answer 3

In practice, you may get the answer faster or slower :-(

There are reasonably good approximations for π (x). So you calculate such an approximation, and if it is too far away you know that π (x) ≠ n. For example, if n ≥ x then I know that π (x) ≠ n without calculating anything.

There is a fast algorithm which determines if π (x) is even or odd, running in O (x^(1/2)). You can run this algorithm and it may detect that the parity of n is wrong and you are done. It has a fifty chance if n is a random integer close to π (x).

Other than that, I don't know of any method that is faster than calculating π (x). Which is very inconvenient - if I write a program that is supposed to calculate π (10^25), and I get a result that isn't obviously wrong, then there is no way to check that my result is correct other than repeating the calculation. And you can't just repeat the calculation using my program, you need to write a different program, otherwise you wouldn't detect if my program has any bugs that make it calculate a slightly different function than π (x).

π (x) can be calculated reasonably easily in about O (n^(2/3)), and faster with some really deep maths.