Timeline for On complexity of a particular prime problem
Current License: CC BY-SA 4.0
3 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 4, 2021 at 4:31 | comment | added | Turbo | It was not clear to me we use polynomial number of calls. I guess it is obvious. | |
| May 4, 2021 at 3:27 | comment | added | Will Sawin | 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. | |
| May 4, 2021 at 1:57 | history | asked | Turbo | CC BY-SA 4.0 |