作者jackliao1990 (j)
看板Gossiping
标题[问卦] AI推翻ETH动摇P!=NP?密码不安全了？
时间Wed Oct 28 13:20:33 2026
昨天OpenAI和Anthropic各自宣布找到指数时间假设(ETH)的反例
两反例不约而同地指向同个极限－最坏情况下时间复杂度皆为2^O(n/(logn)^0.5)
在渐进复杂度上严格小於纯指数时间2^Omega(n)
指数时间假设和千禧年难题P/NP(若一个问题的解可在多项式时间内被验证则该问题是否
也能在多项式时间内被求解？)有关
若指数时间假设为真，则P！=NP
资工界大部份相信P!=NP
AI找到反例後
P!=NP的防线被迫後退
多数码农仍坚信P!=NP
毕竟若P=NP意味着密码可能不安全
以太坊研究员 Justin Drake认为在最坏情况下现行的椭圆曲线签名算法被攻破的时间点
可能会大幅提前（用大型GPU丛集在现有硬体上找出更高效的私钥还原法）
他甚至建议加密行业应着手规划资产大规模迁移
各位认为P等不等於NP?
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 223.138.141.74 (台湾)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Gossiping/M.1793164835.A.4EE.html
1F：→ s72005ming: 何时all in？ 101.10.11.183 10/28 13:22
2F：推 HisVol: 楼下说N = 1就等於 223.137.26.170 10/28 13:32
3F：→ ggirls: 我知道NP=NP 118.231.153.37 10/28 13:35
4F：→ a27588679: 跟我想的差不多 106.1.227.146 10/28 13:39
5F：→ HolyBugTw: 依旧是Exponential，有突破但 P != NP 210.59.207.113 10/28 14:06
6F：→ IBIZA: 不是指数时间了 223.140.129.58 10/28 14:10
7F：→ HolyBugTw: 说错了，SubExponential不是EXP 210.59.207.113 10/28 14:18
8F：→ HolyBugTw: 应该说依旧不是多项式时间 210.59.207.113 10/28 14:19
9F：→ douge: exponentioal sub exponential 永远都140.112.175.204 10/28 21:20
10F：→ douge: 不会是polynomial140.112.175.204 10/28 21:20
11F：→ douge: 两个就是完全不同等级的计算复杂度140.112.175.204 10/28 21:20
12F：→ douge: 这就台大计算理论的期中考题 lol140.112.175.204 10/28 21:21