Schinzel's hypothesis H

Hypothesis H is a variant of the Hardy-Littlewood prime tuples conjecture. It asserts that a non-constant polynomial f(n) with integer coefficients will take infinitely many prime values as long as there is no "obvious" reason for it not to, for instance if it is not coprime to a fixed modulus q for all n, or if it is only positive for finitely many n, or if it factors into polynomials of smaller degree.

It is known for linear polynomials (Dirichlet's theorem), but is open for higher degree (most notably for $n^2+1$).

A stronger version of this hypothesis (the Bateman-Horn conjecture) would assert that there is a k-digit prime of the form f(n) for all sufficiently large n. If this is the case, one can solve the weak version of the finding primes project by searching the k-digit values of a degree d irreducible polynomial, such as $n^d-2$, to find a prime in $O( (10^k)^{1/d} )$ steps for any given d.