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.

Improve this question
$\endgroup$
2
  • $\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, 2015 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, 2015 at 11:21

0

Reset to default

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.