Impagliazzo 五世界图火了：AI 时代密码学命运仍悬而未决
matthew_d_green · x · 2026-11-08
密码学家 Matthew Green 转发一张基于 Impagliazzo 经典 "five worlds" 分类的表格，提醒大家计算复杂度的各种世界至今仍有可能成真。表格列出五种世界及含义：
- Algorithmica（P=NP）：密码学消失，但优化、学习与证明搜索都变容易
- Heuristica（P≠NP 但 NP 问题平均容易）：无密码学，困难实例存在但和求解一样难找
- Pessimoland：困难问题保持困难但无单向函数，被认为是最糟世界
- Minicrypt：单向函数存在但无公钥加密，哈希签名与 AES 存活，无密钥交换
- Cryptomania：公钥加密存在，格、哈希、AES 可用；RSA/ECC 挡不住量子（或 BQP=BQP 时经典也可破）
在 AI 快速进展的当下，这张图被用来提醒：我们仍不知道自己身处哪个世界。
「Fun」频道最新
- 「Gen AI 是史上最大骗局」引战，配图讥讽成 AI 圈名场面素材 — AIandDesign · 2026-11-09
- Ram-Altman：每天给 Sam Altman 发邮件汇报你闲置内存的脚本 — wandedob · 2026-11-09
- 三人三个 Grok Bot 全程代办：免费蹭进健身房零失败 — XFreeze · 2026-11-09
- 印度创业公司 Temple 定价争议：CEO 回应「不为印度制造」 — mgill25 · 2026-11-09
- 神经网络原始汤里的数字生命体：菌丝状演化视觉爆红 — pickover · 2026-11-08
- 99 部手机拉小车，艺术家让 Google Maps 凭空显示堵车 — alifcoder · 2026-11-08