It is said that it is impossible to computationally find the nth prime number in at least O(logn) time complexity. Does there exist a mathematical proof to show this, or is it still an unsolved problem within mathematics? I would like to know if there is a way to computationally solve for the nth prime without solving for the n1, n2, ... prime. And if not, is there a proof showing that this is impossible.

8$\begingroup$ In the standard computation model, just reading the input and writing the output each require $\approx\log n$ time in this case. $\endgroup$ – Emil Jeřábek Oct 16 at 5:26

4$\begingroup$ Computer Science: What is the time complexity of generating nth prime number? It links also to this related question on Theoretical Computer Science: Finding a prime greater than a given bound. (I found also a bit related question on Mathematics: Most efficient algorithm for nth prime, deterministic and probabilistic?) $\endgroup$ – Martin Sleziak Oct 16 at 6:07