Are the Riemann Hypothesis and P vs NP related? It seems that if there is an algorithm to find the distribution of primes without factoring every number would be a polynomial time solution? I am admittedly not a mathematician so this might be a silly question.

  • 3
    $\begingroup$ Prime factorization is not (known to be) NP-complete. Also RH does not provide a better algorithm to find the primes, or to factor numbers. $\endgroup$ – spaceisdarkgreen Sep 25 '18 at 14:25
  • $\begingroup$ Thanks, that basically answers the question. On a somewhat unrelated note wouldn't proving that prime factorization is in fact a P class problem be as big of a deal as proving it is or is not NP-complete? It might not solve P vs NP but demonstrating that it is definitely a P class would have some implications. $\endgroup$ – Matt Sep 25 '18 at 14:40
  • 1
    $\begingroup$ Yes, it would be a big deal, but wouldn't prove P=NP. $\endgroup$ – spaceisdarkgreen Sep 25 '18 at 14:46
  • $\begingroup$ Prime is in fact in P : researchgate.net/publication/2928758_Primes_is_in_P $\endgroup$ – Nicolas FRANCOIS Sep 25 '18 at 14:47
  • 2
    $\begingroup$ @NicolasFRANCOIS Primes (= telling if a number is prime) is not the same as prime factorization, though. $\endgroup$ – Noah Schweber Sep 25 '18 at 15:11

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.