P ≠ NP would not save cryptography: quantum and quantum-gravity computing are the real threat

jamestagg · x · 2026-11-23

The author argues that proving P ≠ NP would not guarantee cryptography's safety, since P vs NP is defined only for classical computers. Quantum computers (BQP) and hypothetical quantum-gravity computers (BQGP) could efficiently solve problems classical machines cannot, breaking crypto even if P ≠ NP holds — and BQGP isn't even formally defined yet. Prior work (Brukner et al., Omri Shmueli et al.) has proposed designs more powerful than ordinary quantum computers. An accompanying graphic lists four ways crypto can still break: quantum algorithms like Shor's, special-purpose exploits, implementation flaws such as side channels, and new physical computation models.

Original post →

More from Safety

Safety channel →