作者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/m.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