If someone finds an efficient way (ridiculous or not) to turn NP into P (such as creating multiple universes, saving the one with the correct answer), would we have any good algorithms for encryption, hashing and so on that are still secure? What other algorithms would become way more efficient? Constant-time sorting? Constant-time SHA256-cracking?

  • $\begingroup$ There's a universe (in fact an infinite number of them) where someone guesses your AES key on the first go. $\endgroup$
    – rath
    Jun 4, 2014 at 1:53
  • $\begingroup$ Sorting is already polynomial time, so $P = NP$ shouldn't matter for that. $\endgroup$
    – otus
    Jun 4, 2014 at 5:46
  • $\begingroup$ SHA-256-cracking (preimage/collision search) is already constant time, too. The implications of P=NP for symmetric primitives are quite complicated. $\endgroup$ Jun 4, 2014 at 7:52


Browse other questions tagged or ask your own question.