回看板
Disp BBS
作者 IBIZA (溫一壺月光作酒)
標題 Re: [問卦] AI推翻ETH動搖P!=NP?密碼不安全了？
時間 Wed Oct 28 15:06:46 2026

※ 引述《jackliao1990 (j)》之銘言：

講得很抽象, 其實沒有那麼難懂

電腦科學上, 演算法有所謂的時間複雜度

也就是一組函數, 你把不同長度或數量的資料丟進去, 得出結果所需要時間


舉一些比較容易理解的時間複雜度


像是常數時間, 不管你丟多複雜的資料進來, 得出結果的時間都一樣

例如: 判斷一個整數是奇數或偶數, 只需要判斷個位數的奇偶

      所以不管給多大的數, 處理時間都一樣


對數時間, 需要的時間是資料量的對數

例如: 用二分搜尋法, 在排序好的數列中找某個數

      每次從中間切開, 判斷大小後, 淘汰一半的數, 所以資料多一倍, 時間只增加1


線性時間, 需要的時間跟資料量成正比, 多一倍的數據就要多一倍的時間

例如: 在無序陣列中, 逐一比對, 搜尋一筆資料, 資料量多一倍, 時間就加倍



二次時間, 需要時間是資料量的平方倍

例如, 泡沫排序法

      這種排序法是把資料從頭開始兩兩比較, 若資料順序不對就交換位置

      處理完第一次之後, 再處理第二次, 直到所有數字排序正確

      所以他需要的處理時間是N*N = N平方


多項式時間, 指的就是時間複雜度可以化成像是 5*N^4+4*N^2這種一元X次方程式

指數時間, 資料量越大, 需要時間呈指數成長的問題, 例如2^n


比較多項式時間跟指數時間

                N=  1     2     3     5     10    20     30    100
==============================================================================
5*N^4 + 4*N^2 :     9    96   441  3225   50400 800160 405萬  5億零4萬

2^N           :     2     4    8    16     1024 104萬  10.73億  1.267*10^30


我們可以發現, 雖然多項式時間增加資料量時間也成長很快

但指數時間是隨資料量爆炸性成長的

在多項式時間跟指數時間之間, 還有次指數時間, 指的是時間沒那麼爆炸成長的

例如2^N開方

指數時間之上, 還有階乘時間跟雙重指數時間



有一些問題, 是已經找到演算法可以在多項式時間內解決的, 稱為P

然後有一些問題, 已知答案驗證對不對, 可以在多項式時間內解決


但要計算答案, 目前還無法找到演算法能在多項式時間內解決, 稱為NP




那甚麼是P=NP跟P!=NP？

P問題能在多項式時間解決, 表示一定也能在多項式時間驗證(解決就是一種驗證)

所以P問題的集合一定在NP集合內

但NP集合是否存在一些P以外的問題, 也就是確實有問題在多項式時間無法驗證

或者目前我們以為的NP問題只是還沒找到演算法, 找到的話, 全部都是P問題

這就是P=NP或P!=NP

https://ibb.co/JRTG1jVJ
[圖]

兩者只要證明其中之一正確, 就解決了這個聖杯

簡單說, 目前OpenAI已經證明NP問題不需要指數時間, 但還沒把時間降到多項式時間


為什麼這個問題在電腦科學很重要？

因為密碼需要能馬上驗證但難以攻破, 也就是NP問題適合拿來編碼

但電腦計算速度跟容量成長很快, 今天難以攻破, 也許幾年後就不難

所以以前都是假設, 這些NP問題是無法在多項式時間解決, 這稱為指數時間假說

然後在這個假設上放心發展密碼學

但如果NP問題最終被證明是多項式時間能解決

那這幾十年的密碼學就要大幅修正了

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 223.140.129.58 (臺灣)
※ 作者: IBIZA 2026-10-28 15:06:46
※ 文章代碼(AID): #1guPyAgC (Gossiping)
※ 文章網址: https://www.ptt.cc/bbs/Gossiping/M.1793171210.A.A8C.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
推 rhox: 跟我想得差不多，我只是懶得寫下來而已1F 36.229.154.233 台灣 10/28 15:07
推 StylishTrade: 他把2^N降到2^(N/logN)這樣有甚麼用就跟你把蘋果皮削掉
說哇蘋果變好小一樣2F 1.163.86.218 台灣 10/28 15:16

指數降到次指數其實難度降很多

但確實目前還沒用, 所以OpenAI也並未宣布證明 P=NP

推 bye2007: 大推 很棒的解說5F 223.143.246.127 台灣 10/28 15:20
※ 編輯: IBIZA (223.140.129.58 臺灣), 10/28/2026 15:22:13
推 StylishTrade: N/logN降很多?6F 1.163.86.218 台灣 10/28 15:26

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