[FOM] Difficult?

[Rahul Santhanam]

> Let n be a specific big integer of some interest. I want to know if
> the number of primes less than n is even or odd.
>
> DIGRESSION. Is the set of all positive integers n in base 2 such that
> the number of primes less than n is even, #P-complete in the sense of
> computational complexity theory? Same question with regard to the
> function f(n) = the number of primes less than n.
>

Mod_{2}P is the class of languages whose characteristic function is the
low-order bit of a #P function. The existence of a poly-time algorithm for
primality testing immediately implies that Harvey's set is in Mod_{2}P.

It is commonly believed that Mod_{2}P is not as "powerful" as #P. However,
there is a beautiful theorem of Toda which states that every language in
the poly-time hierarchy can be reduced to a language in Mod_{2}P via
randomized reductions. Results in the theory of derandomization further
suggest that the reductions can be made deterministic.

This still does not answer the original question about hardness. A
hardness result would probably be quite difficult to show as it would
effectively imply that there is no poly-time algorithm for computing f(n).

Rahul.