Intereting Posts

Simplify $\sqrt n+\frac {1}{\sqrt n}$ for $n=7+4\sqrt3$
How to compute the integral closure of $\Bbb{Z}$ in $\mathbb Q(\sqrt{p})$?
Intuition for dense sets. (Real analysis)
Can I apply the Girsanov theorem to an Ornstein-Uhlenbeck process?
Possibly not an acceptable proof for uncountablity of countable product of countable sets
Formula for curve parallel to a parabola
Find $f(x)$ such that $f(f(x)) = x^2 – 2$
When is an operator on $\ell_1$ the dual of an operator on $c_0$?
derivation of fibonacci log(n) time sequence
Is there a $k$ such that $2^n$ has $6$ as one of its digits for all $n\ge k$?
Sum of reciprocals of product of consecutive integers
The $n$th term of this infinitely nested radical sequence
Isomorphism on Cohomology implies isomorphism on homology
Continuity question: Show that $f(x)=0, \forall x\in\mathbb{R}$.
Matrix derivative $(Ax-b)^T(Ax-b)$

Is there a polynomial-time algorithm to find a prime larger than $n$?

If Cramér’s conjecture is true, we can use AKS to test $n+1$, $n+2$, etc. until the next prime is found, and this method will find a prime in polynomial time (in $\log n$) because AKS runs in polynomial time and Cramér’s conjecture guarantees $O((\log{n})^2)$ primes to test.

Without assuming Cramér’s conjecture, and without requiring that the prime to be found is the next prime following $n$, only that it is larger than $n$, can such a prime be found in time $O((\log{n})^k)$ for some $k$?

- Counting primes
- Which is asymptotically larger: $\lg(\lg^* n)$ or $ \lg^*(\lg n)$?
- How to check if any subset of a given set of numbers can sum up to a given number
- Algorithm for scrolling through different orbits in a permutation group
- Algorithm for constructing primes
- Fastest Square Root Algorithm

This question is motivated by some thoughts I wrote about in the comments on this answer by Gerry Myerson.

- Number of integer solutions: $x^2 + y^2 + z^2 = N$
- Why is convexity more important than quasi-convexity in optimization?
- Largest idempotent
- Any problem computable in $k$ memory slots can be computed with polynomials.
- What would be the shortest path between 2 points when there are objects obstructing the straight path?
- Lattice generated by vectors orthogonal to an integer vector
- Reasoning the calculation of the Hilbert's distance
- Algorithm for constructing primes
- finding if two binary quadratic forms represent the same integers
- Heronian triangle Generator

This is Rick Sladkey’s comment as a CW answer. An algorithm is given in this paper: “Deterministic Methods to Find Primes”.

- Conceptual question about Locally Convex Spaces
- What is the meaning of the third derivative of a function at a point
- If $\sin A + \cos A + \tan A + \cot A + \sec A + \csc A = 7$ then $x^2 – 44x – 36 = 0$ holds for $x=\sin 2A$
- Intersection between two lines
- $\mathbb{Q}/\mathbb{Z}$ has a unique subgroup of order $n$ for any positive integer $n$?
- Finding a basis for the field extension $\mathbb{Q}(\sqrt{2}+\sqrt{4})$
- Concurrent lines proof for a regular 18-gon
- Is it always safe to assume that a integral is zero if it has equal bounds?
- Counting symmetric unitary matrices with elements of equal magnitude
- Must $k$-subalgebra of $k$ be finitely generated?
- Intersection of finitely generated ideals
- How to show a sequence of independent random variables do not almost surely converge by definition?
- How to prove that a conditionally convergent series can be rearranged to sum to any real number?
- $K_n$ as an union of bipartite graphs
- Detecting symmetric matrices of the form (low-rank + diagonal matrix)