0
$\begingroup$

Is the following problem in $PH$ and is it complete for any class?

Problem: Is the $i$th bit of the $m$th prime $1$?

It appears to require a counting quantifier which has to demonstrate witness is the $m$th prime and since there is an unique witness is it in $UP^{PP}$?

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ It's in $P^{PP}$ because if you have an oracle that tells you the number of primes up to $n$ (which is in $PP$) then you can find the $m$th prime rapidly by binary search. $\endgroup$
    – Will Sawin
    Commented May 4, 2021 at 3:27
  • $\begingroup$ It was not clear to me we use polynomial number of calls. I guess it is obvious. $\endgroup$
    – Turbo
    Commented May 4, 2021 at 4:31

0

Reset to default

You must log in to answer this question.