回看板
Disp BBS
作者 jackliao1990 (j)
標題 [問卦] 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 (臺灣)
※ 作者: jackliao1990 2026-10-28 13:20:33
※ 文章代碼(AID): #1guOOZJk (Gossiping)
※ 文章網址: https://www.ptt.cc/bbs/Gossiping/M.1793164835.A.4EE.html
※ 同主題文章:
[問卦] AI推翻ETH動搖P!=NP?密碼不安全了？
10-28 13:20 jackliao1990
Re: [問卦] AI推翻ETH動搖P!=NP?密碼不安全了？
10-28 15:06 IBIZA
Re: [問卦] AI推翻ETH動搖P!=NP?密碼不安全了？
10-28 20:48 orze04
→ s72005ming: 何時all in？1F 101.10.11.183 台灣 10/28 13:22
推 HisVol: 樓下說N = 1就等於2F 223.137.26.170 台灣 10/28 13:32
→ ggirls: 我知道NP=NP3F 118.231.153.37 台灣 10/28 13:35
→ a27588679: 跟我想的差不多4F 106.1.227.146 台灣 10/28 13:39
→ HolyBugTw: 依舊是Exponential，有突破但 P != NP5F 210.59.207.113 台灣 10/28 14:06
→ IBIZA: 不是指數時間了6F 223.140.129.58 台灣 10/28 14:10
→ HolyBugTw: 說錯了，SubExponential不是EXP
應該說依舊不是多項式時間7F 210.59.207.113 台灣 10/28 14:18

--
作者 jackliao1990 的最新發文:
點此顯示更多發文記錄