0

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.

Matt
  • 109
  • 3
    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. – spaceisdarkgreen Sep 25 '18 at 14:25
  • 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. – Matt Sep 25 '18 at 14:40
  • 1
    Yes, it would be a big deal, but wouldn't prove P=NP. – spaceisdarkgreen Sep 25 '18 at 14:46
  • Prime is in fact in P : https://www.researchgate.net/publication/2928758_Primes_is_in_P – Nicolas FRANCOIS Sep 25 '18 at 14:47
  • 2
    @NicolasFRANCOIS Primes (= telling if a number is prime) is not the same as prime factorization, though. – Noah Schweber Sep 25 '18 at 15:11

0 Answers0