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 '14 at 1:53
  • $\begingroup$ Sorting is already polynomial time, so $P = NP$ shouldn't matter for that. $\endgroup$ – otus Jun 4 '14 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$ – Dmitry Khovratovich Jun 4 '14 at 7:52

Browse other questions tagged or ask your own question.