5
$\begingroup$

I'm wondering what are the current known uses/implications of a polynomial-time algorithm for the following problem:

Given $n$ in binary, output a prime $p > n$.

I'm both curious about specific useful applications, and any more broad complexity implications (for instance, would this get us any closer to $P=BPP$?).

Edit: by the way, this problem was (is?) the subject of the Polymath4 project, which produced this writeup, but I do not see anywhere that they discuss implications of truth of the conjecture.

| cite | improve this question | |
$\endgroup$
  • $\begingroup$ This is likely true since it is conjectured that the prime gap is O(log(p_n)^2): en.wikipedia.org/wiki/Cram%C3%A9r%27s_conjecture $\endgroup$ – joro Jan 23 '15 at 7:56
  • 1
    $\begingroup$ @joro, agreed that it is likely true (although I am not sure if Cramer's conjecture is generally conjectured). There are interesting consequences of lots of things we think are likely true but cannot currently prove.... $\endgroup$ – usul Jan 23 '15 at 11:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.