Deciding whether an interval contains a prime number What is the complexity of deciding whether an interval of the natural numbers contains a prime? A variant of the Sieve of Eratosthenes gives an $\tilde O(L)$ algorithm, where $L$ is the length of the interval and $\sim$ hides poly-logarithmic factors in the starting point of the interval; can we do better (in terms of $L$ alone)?
Disclaimer: I'm not an expert in number theory.

Short answer: If you're willing to assume "reasonable number-theoretic conjectures", then we can tell whether there is a prime in the interval $[n, n+\Delta]$ in time $\mathrm{polylog}(n)$. If you're not willing to make such an assumption, then there is a beautiful algorithm due to Odlyzko that achieves $n^{1/2 + o(1)}$, and I believe that this is the best known.

Very helpful link with lots of great information about a closely related problem: PolyMath project on deterministic algorithms for finding primes.

Long answer:

This is a difficult problem, an active area of research, and seems to be intimately connected to the difficult question of bounding gaps between the primes. Your problem is morally very similar to the problem of finding a prime between $n$ and $2n$ deterministically, which was recently the subject of a PolyMath project. (If you want to really dive into these questions, that link is a great place to start.) In particular, our best algorithms for both problems are essentially the same.

In both cases, the best algorithm depends heavily on the size of gaps between the prime. In particular, if $f(n)$ is such that there is always a prime between $n$ and $n + f(n)$ (and $f(n)$ can be computed efficiently), then we can always find a prime in time $\mathrm{polylog}(n) \cdot f(n)$ as follows. To determine whether there is a prime between $n$ and $n + \Delta$, first check if $\Delta \geq f(n)$. If so, output yes. Otherwise, just iterate through the integers between $n$ and $n + \Delta$ and test each for primality and answer yes if you find a prime and no otherwise. (This can be done deterministically, which is why deterministically finding a prime between $n$ and $2n$ is so closely related to determining whether there is a prime in a certain interval.)

If the primes behave like we think they do, then this is the end of the story (up to $\mathrm{polylog}(n)$ factors). In particular, we expect to be able to take $f(n) = O(\log^2 n)$. This is known as Cramér's conjecture after Harald Cramér, and proving it seems very far out of reach at the moment. But, as far as I know, it is widely believed. (One arrives at this conjecture, e.g., from the heuristic that the primes behave like the random set of integers obtained by including each integer $n \geq 3$ independently at random with probability $1/\log n$.)

There are many conjectures that imply the much much weaker bound $f(n) \leq O(\sqrt{n})$, such as Legendre's conjecture. (I'm not aware of any conjectures that are known to imply an intermediate bound, though I imagine that they exist.) And, the Riemann hypothesis is known to imply the similar bound $f(n) \leq O(\sqrt{n} \log n)$. So, if you assume these conjectures, you essentially match Odlyzko's algorithm (up a factor of $n^{o(1)}$) with a much simpler algorithm.

I believe that the best unconditional bound right now is $\widetilde{O}(n^{0.525})$ due to Baker, Harman, and Pintz. So, if you assume nothing, then Odlyzko's algorithm beats the obvious algorithm by roughly a factor of $n^{0.025}$.