Re: [其他] 見證奇蹟的時刻 NP=P
※ 引述《gj942l41l4 (豔鵪鶉)》之銘言：
: 我也想問一下很多人在問的問題，就是
: 如果真的証明P=NP了，對這個世界會造成什麼影響嗎@@?
: 我不是資訊或數學系的
: 對P、NP的了解大概也只有LPH66大大寫的那篇@@
: 有個例子是說質因數太快被分解的話我們的密碼學會崩盤（沒會錯意吧..）
: 我在想，根據 Weierstrass Approximation Theorem
: 在閉區間中的連續函數都可以用多項式函數來近似
: 反過來看
: 對連續函數，都存在著"不會收斂比較快的多項式函數"
: 也就是說，即使証明了P=NP，或甚至P=全世界可解的問題
: 但找的到多項式解是一個不比原本演算法來得快的解法
: 這樣對這世界的進步是否也有限呢？
: 那麼目標是否該是對問題找個簡單的解法（但這又回到沒系統性的一一擊破了..）
: 為何人類這幾十年來會執著於P=NP的証明上呢？
: 真的滿好奇的，希望熟悉的大大解答@@
好像一直有版友以為 P=NP 的問題是因為實用上追求更快的演算法而產生的
並不全然如此, 歷史上這問題的根源非常早
以下說的是我記憶和理解中的部份, 因為這問題太大, 就只能大概說說,
細節可能有誤, 那是一定的, 因為這些內容牽涉太多層面, 我只能概述,
看有沒有強者做補充.
純粹從數學的觀點來看, 計算理論的問題可以追溯到希爾伯特和羅素他們
為了要驗證公理系統的一致性, 而希望把整個公理系統用一階符號邏輯來表示
這部份在數理邏輯的發展最後導致了Godel著名的不完備定理
而和計算理論直接相關的, 則是 Alan Turing 他們, 在之後不久,
提出了 Turing machine 等模型, 做為邏輯演算的一種形式模型.
那時候還沒有現代的電子計算機, 他們提出的是理論上的抽象的模型.
P和NP中所說的 deterministic 和 nondeterministic turing machine
說的就是他們提出的 turing machine 這種模型
Godel的不完備定理, 對應到計算理論上面, 也有類似的問題, 例如 Turing machine上
著名的 Halting problem. 這個問題用現代電腦的語言來說的話, 就是:
要如何寫一個程式A, 這個程式A可以檢查出隨意一個程式B是否有可能陷入無限執行
(比如有無限迴圈的bug)的bug?
比方說某甲設計了一個程式B, 本來當變數 x <0時就要跳出迴圈程式結束. 然而程式B
是否可能遇到某種 input 使得 x 永遠大於 0? 程式A就是要用來檢查隨意一個程式B是
否會發生這種可能性. 答案是程式A不可能存在.
後來隨著電子計算機的發展, 電腦被用來解各種問題, 從線性規劃到finite element
到銀行利率各式各樣的問題, 演算法也發展得越來越複雜. 但是在理論上可以證明,
現在所用的電子計算機, 它運算的能力, 和 Turing machine 這個理論模型是等價的.
也就是說, 凡是能用現在的電腦所設計出來的演算法, 也就能設計出一個等價的Turing
machine, 反之亦然. 而Halting problem 或者某類覆蓋問題等這種在Turing machine
上沒有演算法的問題(稱做 undecidable problems)也還是無解.
然而, 理論歸理論, 工程師們發現, 並不是每個實際上遇到的問題都差不多.
雖然每個問題他們都可以設計出演算法, 但有些問題他們想不出 "好的"演算法.
什麼演算法叫做 "好的"? 在196x年時, 只是一個很模糊的概念, 他們發現大致上可以
把實用問題分成兩類, 其中一種如矩陣運算, 配對問題, 都有很快的運算法, 另一種
如某些工作排程問題, 電腦卻解得非常吃力. 之後就有人提出"好的"演算法是在
多項式時間可以完成的這種概念.
然後在 196x年末, 以及約1972年時, Levin和Cook等人建立了NP-complete的理論.
這個理論把可以用 deterministic turing machine 在多項式時間解決的問題,
歸入集合 P, 可以用 nondeterministic turing machine 在多項式時間解決的問題,
歸入集合 NP. 然後他們找到了一類問題叫做 NP-complete, 只要這個集合中的
任何一個問題屬於 P, 那麼 NP就會等於 P.
而實用上, NP-complete問題正好就差不多等於那些工程師們在經驗上覺得困難的問題,
於是許多人就直接用 "某個問題是 NPC" 來表示某個問題在實用上沒有好方法.
但這個說法只是方便, 並不準確. 而NP等於P在實用上是不是會造成重大衝擊?
我個人認為不至於.
第一, 我們現在用的電腦只是其中一種計算機, 還有各種可能的機器待被發現, 現在難
的問題以後不見得是難題, 不管NP是不是等於P.
第二, 現在最困難的, 並不是Hamiltonian cycle之類的 NPC 問題. NPC問題許多都有所
謂的 Heuristic演算法或是 approximation演算法. 在實用上已經夠了. 比方說我們人類
基因定序等問題, 雖然是 NPC, 但是電腦跑跑 approximation, 問題基本解決.
最難的, 是人工智慧. 如果有部電腦可以通過 turing test, 會對人類世界造成非常大
的衝擊. 所謂 turing test簡單說就是, 把一台電腦和一個真人放在兩個房間裡, 房間
外的人可以對兩個房間提出任意問題, 一直到他們認為可以區分出哪個房間是電腦, 哪
個房間是人. 如果他們總是無法區分出來, 或是答對的機率只有一半, 那麼這台電腦就
算通過 turing test. 這個比 NP 是不是等於 P影響更大得多.
第三, 如果 NP等於 P, 是不是仍然有些問題需要很高次方的多項式演算法? 一定有, 但
經驗告訴我們, 目前絕大多數有多項式演算法的實用上有意義的問題, 它們的次方都很
低. 四次就算高的. 如果我們對 Hamiltonian cycle問題找到一個 10次方的演算法,
以目前電腦的速度, 除非問題輸入的 graph非常非常大, 否則對電腦而言也不過是小菜
一碟.但如果 NP 不等於 P, 問題的輸入只要稍大一些, 就要跑幾個月. 所以沒
有人擔心NP即使等於P, Hamiltonian cycle的演算法是不是要100次方. 目前我們遇到的
所有有實用價值的問題, 連10次方的都沒看過.
既然 NP等不等於P在實用上不見得會造成衝擊, 那麼討論它的意義在哪裡?
NP等不等於P, 雖是演算法問題, 但本質上, 是個邏輯問題. 從希臘人開始研究古典
邏輯學以來, 到了德國哲學家康德中間過了一千多年, 世人認為邏輯學已經結束了.
結果形式邏輯的發展, 徹底地改變了人類對邏輯的認知. 現在距離Godel的不完備定理,
也超過80年了, 從 turing machine 的提出一直到 NP-complete 理論的, 感覺好
像能探討的也差不多了. 但我們卻無法回答, 到底 deterministic turing machine
和 nondeterministic turing machine 之間是否有那道鴻溝? 有些人覺得, 除非有
突破性的想法, 否則無法解決這問題. 有位大陸的教授, 現在在美國教書. 他曾對
我說, 他審 NP等不等於P的論文, 首先看論文裡有沒有任何新的性質, 只要他一眼
望去沒看到任何他認為新的東西, 那麼他連看都不看就直接reject. 他們認為,
這問題會帶領我們進入一個新境界, 就像當初 Godel的不完備定理所帶來的衝擊
(也許沒那麼大, 但也夠了)那樣. 所以它是一個非常重要的問題. 至於是不是真的
這樣, 我也不知道, 但我希望是.
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 221.169.231.152
推
06/02 17:09, , 1F
06/02 17:09, 1F
推
06/02 17:24, , 2F
06/02 17:24, 2F
你還可以問, 判斷圍棋的征子成不成立是什麼問題? 會比踩地雷難嗎?
判斷征子不是很簡單嗎? 但征子成不成立是 PSpace-complete, 比 NP 更高一級
如果這樣就能說服別人征子是個難題, 那麼就不會有人願意出100萬美金解決NP=P問題了
※ 編輯: id010406 來自: 221.169.231.152 (06/02 17:37)
推
06/02 17:50, , 3F
06/02 17:50, 3F
征子就是一連串的叫吃, 最後把對方逼到無路的一種圍棋走法. 這要有圖才比較好說明,
總之是初學者就學會的走法. 如果你有會下圍棋的朋友, 你告訴他判斷征子成不成立是
一個很難很難比踩地雷破密碼都難的問題, 他一定會覺得你在唬爛, 因為我告訴別人這
件事時, 沒有一個人相信. 他們會覺得你根本就是不懂, 然而事實就是這樣.
※ 編輯: id010406 來自: 221.169.231.152 (06/02 18:00)
推
06/02 18:02, , 4F
06/02 18:02, 4F
推
06/02 19:06, , 5F
06/02 19:06, 5F
推
06/02 19:27, , 6F
06/02 19:27, 6F
推
06/02 20:57, , 7F
06/02 20:57, 7F
推
06/02 21:00, , 8F
06/02 21:00, 8F
推
06/03 01:49, , 9F
06/03 01:49, 9F
推
06/03 03:05, , 10F
06/03 03:05, 10F
推
06/03 06:10, , 11F
06/03 06:10, 11F
推
06/03 13:22, , 12F
06/03 13:22, 12F
複雜度有分兩種, 一種是時間複雜度, 一種是空間複雜度
P 和 NP 指的是時間複雜度, 直觀地用電腦比喻, 就是一個程式執行起來,
需要多少時間(或者說要執行幾個指令)
凡是屬於P的問題, 都可以設計出一個在多項式時間內就能解決問題的程式.
而PSPACE 和 Log Space 指的是空間複雜度, 直觀地用電腦比喻,
就是一個程式執行過程, 會佔用多少記憶體
PSPACE 指的是這個問題, 可以設計出一個佔用多項式記憶體就把它解決的程式.
比方我們要解 n 個 m*m 矩陣的乘法, 加法等一連串運算.
n 個 m*m 的矩陣相乘, 寫個最簡單的程式 O(n*m^3) 就能解決, 所以這個問題屬於 P.
而我們這個程式在執行的時候, 用了一個 m*m的矩陣暫存運算的中間結果,
也就是空間複雜度是 O(m^2), 所以這個問題也屬於 PSPACE
1. derterministic 或 nonderterministic 只影響時間複雜度, 但對空間複雜度來說
不重要. 目前不知道 P 是否等於 NP, 但 PSPACE=NPSPACE
2. PSPACE 包含或等於 NP, 也就是說凡是屬於 NP的問題都可以用多項式空間就解決,
但反之不一定.
征子是 PSPACE-complete的證明可以搜尋關鍵字 "ladders are pspace complete"
以下是其中一個 source http://dl.acm.org/citation.cfm?id=647481.728110
證明的方法就和前面 LPH66 大所講的踩地雷證法的原理是一樣的, 其他就請強者補充了
我發覺講了半天我竟然沒寫 deterministic 和 nonderterministic turing machine
的定義 :Q 不過還是交給強者, 我只補充說一下為什麼這些運算問題是邏輯問題.
現在我們用的電腦, 它做整數除法, 其實是做了一連串的邏輯運算. 考慮一艘在外太空
故障的太空船, 沒有紙筆和電腦可以使用, 但是太空人必須在一秒內算出兩個大整數
p, q相除的結果, 準確到小數點下10位, 即時修正航線, 否則就會失事.
於是他們就把一些砝碼湊成 q, 然後裝上一個引擎, 施力 p, 而他們還有一個很準確的
測速器, 在一秒後, 測出砝碼的速度 v到小數點下10位, 根據牛頓第二定律 v=p/q
於是這整個砝碼, 引擎, 測速器等, 就構成了一個做除法的計算機.
計算機並不是只侷限在我們現在所用的電腦, 事實上世間萬物每秒都在運算. 但是上面
那個太空船的計算機, 和電腦不同的是, 它做除法並不是做邏輯運算. 這種計算機如果
測速器更精準一些, 那就可以在更少的時間內, 算出更大的整數相除, 到小數點下更多
位數, 甚至比我們用電腦還快. 可是因為量子力學的限制, 它會有一個極限. 這種計
算機能算多快, 是一個物理問題.
如果 Hamitonian cycle 這個NP-complete的問題, 也有像整數除法一樣, 有個對應的
物理計算機, 那麼它能多快時間解出來, 就是個物理問題, 和P等不等於NP無關.
而 turing machine 做的是邏輯運算, 某個問題能不能在多項式個步驟就完成, 並不是
由量子力學來決定. 它是邏輯運算能多快的問題. 大致很粗略的想法就大概是這樣.
※ 編輯: id010406 來自: 221.169.231.152 (06/03 15:05)
推
06/04 01:01, , 13F
06/04 01:01, 13F
用比較直觀的說法, 一部計算機, 如果它有個 cpu, 而這 cpu的所有可能狀態是有限的,
就叫做 "有限狀態機", 比方我們現在使用的電腦就是.
如果有限狀態機還有一塊無限大的記憶體, cpu有個讀寫頭可以讀寫記憶體, 那麼它解
決問題的能力就和turing machine等價.
而如果cpu根據它目前的狀態, 就決定了它下一步要做哪一個指令, 那就叫
deterministic 機器. 我們現在使用的電腦就是 deterministic machine.
如果cpu下一步會做哪一個指令, 是一個可能的集合, 並不唯一, 那就叫
nondeterministic 機器. 重點在於, 它會執行集合中哪個指令, 並不是隨機的, 而是它有
"無限洞察力". 也就是說, 如果這個問題有解, 那麼這個 cpu 就會在所有可能的指令
中, 執行會解決問題的那個指令, 好像它已經知道答案是什麼那樣.
比方我們要解這個版上出現過的問題: 在 1到 100間, 是否能找出不同的8 個整數,
使得它們的倒數和等於 1?
一個 可能的 deterministic 程式, 有 8層迴圈
for(x1=2 to 93) for(x2=x1+1 to 94) for(x3=x2+1 to 95).....
for(x8=x7+1 to 100)
{
if (1/x1+1/x2+1/x3+...+1/x8==1) then return x1 x2 x3....x8
}
最壞可能要做 O(100^8) 那麼多組
但是 nondeterministic 程式, 只要做 8 步
1. 在 1到93之間選一個數為 x1
2. 在 x1+1 到94間 選一個數 為 x2
....
8. 在 x7+1 到 100 間選一個數 為 x8
return x1 x2 x3....x8
這個程式每一步會選哪個數字並不是隨機亂選, 因為它有 "無限洞察力", 如果 x1=3
有一組解, 那麼cpu執行第一行就會把 x1 設為 3. 接下來如果 x2=7 有一組解, 那麼
第二行就會把 x2 設為 7, 如此繼續下去.
這種機器當然只是理論上的. 這種理論有什麼意義? 有人可能會懷疑這和算命仙的水晶
球有什麼不一樣.
差別在於, 我們問算命師ABC猜想成立嗎? 他只告訴我們是或否, 至於相不相信, 在個人.
但是 nondeterministic machine 是一位 "超級數學家", 你問他ABC猜想成立嗎?
他說是, 然後你說證明給我看, 他就開始打出一串證明, 告訴你第一步你要選什麼,
第二步你又要做什麼,依次做給你看.
也就是說, 我們不知道這位數學大師怎麼推理的, 可是他會有個證明讓你檢驗, 而如
果這個檢驗只需花多項式個步驟, 那麼這個問題就屬於 NP
比方說, 或許我們窮一生之力的時間也無法證明ABC猜想, 因為有太多可能性, 但一旦
有一位大師寫出證明, 我們或許只要一個星期就能驗證這證明是對的.
而 Cook 的貢獻, 就是證明了一個特殊的問題: propositional logic的 satisfiability
問題, 簡稱 SAT. 只要存在一個多項式個步驟就能解決SAT的演算法, 那麼對那些屬於NP
的問題, 也就是在多項式個步驟內就能驗證的問題, 我們不需要這位 "超級數學家", 自
己就能在多項式個步驟裡找到證明.
所以只要SAT有很快的演算法可以解決, 也就是說如果 NP=P, 那就幾乎如同我們在NP
問題方面具有 "無限洞察力"一樣, 這當然是相當不可思議的事情. 所以了解NP會不會
等於P在理論上很重要.
但問題是, 像ABC猜想那類的問題, 是屬於所謂的 PSPACE 而不是 NP. 因為用來
表達大多數學公理系統的, 是所謂的 first order logic, 一階符號邏輯. 這類問題
是 PSPACE-complete, 它有時候即使是驗證證明的對錯也需要指數式個步驟. 更糟
的情形就是 Kurt Godel證明的, 有些定理沒有辦法從這個公理系統得到證明或反證.
遇到這種情況, nondeterministic machine 這位超級數學家會無限地執行下去, 而我們
不知道他會不會停.
所以即使我們對NP問題有了無限洞察力, 應該也還是有很多工作要做.
※ 編輯: id010406 來自: 221.169.231.152 (06/04 23:53)
推
06/05 23:00, , 14F
06/05 23:00, 14F
推
07/28 05:23, , 15F
07/28 05:23, 15F
→
11/10 11:54, , 16F
11/10 11:54, 16F
→
01/02 15:26,
7年前
, 17F
01/02 15:26, 17F
→
07/07 11:06,
6年前
, 18F
07/07 11:06, 18F
討論串 (同標題文章)