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.
More from Safety
- Harvard Law Scholar Uses Canine Law Framework to Assign Liability for Rogue AI Agents — bigdata · 2026-11-23
- OpenAI out-Anthropic-ing Anthropic on safety vibes, observers say — shakoistsLog · 2026-11-23
- Aletheia Aegis: Open-Source MCP Server Blocks Leaky Agent Outputs in ~0.02ms — Fuzzy-Ad9840 · 2026-11-23
- Erik Hoel's Bicameral Labs proposes 'qualiaphobic' AI architectures provably hostile to consciousness theories — erikphoel · 2026-11-23
- Canary tokens in ~2M AI requests expose breaches at 3 providers and broken ZDR promises — ccerrato147 · 2026-11-23
- prompt2pwn AI hacking event wraps: 5 major targets, world-class speakers, standout CTF — rez0__ · 2026-11-23