作者hcsoso (索索)
看板Math
標題Re: [其他] 見證奇蹟的時刻 NP=P
時間Sun Jun 2 22:51:38 2013
LPH66 與 id010406 板友都已經說了不少,
我也試著寫一些個人對於 P vs NP 問題的看法好了.
※ 引述《id010406 (no id)》之銘言：
: 好像一直有版友以為 P=NP 的問題是因為實用上追求更快的演算法而產生的
: 並不全然如此, 歷史上這問題的根源非常早
: 以下說的是我記憶和理解中的部份, 因為這問題太大, 就只能大概說說,
: 細節可能有誤, 那是一定的, 因為這些內容牽涉太多層面, 我只能概述,
: 看有沒有強者做補充.
: 純粹從數學的觀點來看, 計算理論的問題可以追溯到希爾伯特和羅素他們
: 為了要驗證公理系統的一致性, 而希望把整個公理系統用一階符號邏輯來表示
: 這部份在數理邏輯的發展最後導致了Godel著名的不完備定理
: 而和計算理論直接相關的, 則是 Alan Turing 他們, 在之後不久,
: 提出了 Turing machine 等模型, 做為邏輯演算的一種形式模型.
: 那時候還沒有現代的電子計算機, 他們提出的是理論上的抽象的模型.
: P和NP中所說的 deterministic 和 nondeterministic turing machine
: 說的就是他們提出的 turing machine 這種模型
當然提到 Turing machine 就得要提到 Church-Turing thesis.
這個 thesis (當然, 不能證明) 宣稱:
任何能力夠強的運算機器都等價於 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)也還是無解.
是的, 這些仍都是計算理論的領域. 而 P vs NP 則是在複雜度理論中的問題;
它所在意的不是可否計算, 而是可否 "快速" 計算.
: 然而, 理論歸理論, 工程師們發現, 並不是每個實際上遇到的問題都差不多.
: 雖然每個問題他們都可以設計出演算法, 但有些問題他們想不出 "好的"演算法.
: 什麼演算法叫做 "好的"? 在196x年時, 只是一個很模糊的概念, 他們發現大致上可以
: 把實用問題分成兩類, 其中一種如矩陣運算, 配對問題, 都有很快的運算法, 另一種
: 如某些工作排程問題, 電腦卻解得非常吃力. 之後就有人提出"好的"演算法是在
: 多項式時間可以完成的這種概念.
提出這個理論的人是 Edmonds, 在他 1965 年的論文 "Paths, trees, and flowers" 中
提供了一個 O(n^4) 的演算法來解決任意圖上的配對問題; 同時他也提出了
多項式時間演算法 <=> 快速演算法
的概念.
: 然後在 196x年末, 以及約1972年時, Levin和Cook等人建立了NP-complete的理論.
: 這個理論把可以用 deterministic turing machine 在多項式時間解決的問題,
: 歸入集合 P, 可以用 nondeterministic turing machine 在多項式時間解決的問題,
: 歸入集合 NP. 然後他們找到了一類問題叫做 NP-complete, 只要這個集合中的
: 任何一個問題屬於 P, 那麼 NP就會等於 P.
: 而實用上, NP-complete問題正好就差不多等於那些工程師們在經驗上覺得困難的問題,
: 於是許多人就直接用 "某個問題是 NPC" 來表示某個問題在實用上沒有好方法.
Cook 與 Levin 獨立的證出了所有 NP 的問題都可以化為 SAT 問題,
因此第一次能夠證明有問題為 NP-complete.
接著 Karp 發表一篇論文將當時大家不知道怎麼解的問題歸納整理為 21 個,
然後利用 Cook-Levin 的結果證明了它們通通是 NP-complete,
也因此提供了這套理論十分重要的證據.
: 但這個說法只是方便, 並不準確. 而NP等於P在實用上是不是會造成重大衝擊?
: 我個人認為不至於.
: 第一, 我們現在用的電腦只是其中一種計算機, 還有各種可能的機器待被發現, 現在難
: 的問題以後不見得是難題, 不管NP是不是等於P.
最大的問題是 P vs NP 與能夠解 SAT (或任何 NPC 問題) 的演算法之間的好壞沒有
直接關係; 想像 (1) P = NP 且 SAT 最快只有 n^(10^100) 演算法, (2) P = NP 且 SAT
能有 n^2 演算法(並且常數夠小), (3) P != NP 且 SAT 有 1.0000000001^n 演算法,
你就知道這三個世界的差別了. Impagliazzo 曾經寫過一篇文章
A personal view of average-case complexity,
其中在描述這幾種世界的不同以及對現實生活的影響, 有興趣可以看看.
: 第二, 現在最困難的, 並不是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次方的都沒看過.
定義有實用價值這件事不是個數學問題.
而有發表過的文章中, 有接近天文數字的多項式時間:
http://cstheory.stackexchange.com/q/6660/1800
: 既然 NP等不等於P在實用上不見得會造成衝擊, 那麼討論它的意義在哪裡?
: NP等不等於P, 雖是演算法問題, 但本質上, 是個邏輯問題. 從希臘人開始研究古典
: 邏輯學以來, 到了德國哲學家康德中間過了一千多年, 世人認為邏輯學已經結束了.
: 結果形式邏輯的發展, 徹底地改變了人類對邏輯的認知. 現在距離Godel的不完備定理,
: 也超過80年了, 從 turing machine 的提出一直到 NP-complete 理論的, 感覺好
: 像能探討的也差不多了. 但我們卻無法回答, 到底 deterministic turing machine
: 和 nondeterministic turing machine 之間是否有那道鴻溝? 有些人覺得, 除非有
: 突破性的想法, 否則無法解決這問題. 有位大陸的教授, 現在在美國教書. 他曾對
: 我說, 他審 NP等不等於P的論文, 首先看論文裡有沒有任何新的性質, 只要他一眼
: 望去沒看到任何他認為新的東西, 那麼他連看都不看就直接reject. 他們認為,
: 這問題會帶領我們進入一個新境界, 就像當初 Godel的不完備定理所帶來的衝擊
: (也許沒那麼大, 但也夠了)那樣. 所以它是一個非常重要的問題. 至於是不是真的
: 這樣, 我也不知道, 但我希望是.
我仍然認為 P vs NP 是個重要性不亞於 Riemann hypothesis 的數學問題.
即使它的來源是電腦科學, 並不代表它必須要有應用才是個重要的問題.
就像了解 Riemann hypothesis 幫助我們了解質數(還有許多?),
了解 P vs NP 幫助我們了解什麼是計算的效率.
更別說如果 P = NP 且我們有速度快的演算法的話,
所有數學證明就都可以自動化了, Riemann hypothesis 就有望了...
最根本的問題是, 我們對這個題目了解太少了.
我們連證明 SAT 問題不能在 n^1.0000000001 時間內解決都做不到!
因此目標若是證明 P != NP, 這樣一步登天幾乎是不可能的;
更別提目前大家歸納出來證明 P != NP 的各樣錯誤證法,
所有錯誤的證明幾乎都犯了這些錯誤.
至於證明 P = NP, 雖說提出一個多項式時間演算法看似簡單,
但演算法的正確性證明與時間分析似乎沒有一篇證明是完整的;
我猜這篇論文的正確性證明應該也是有問題的.
(當然我沒有細看, 但是看到一個地方覺得他事情都沒有講清楚就放棄了;
而在那之前的定義都太單純了, 沒有什麼新東西.)
還有很多故事可以說, 不過最近有一位複雜度理論的教授出了第一本 P vs NP 的
科普書, 很推薦大家借來看看, 寫的相當淺顯易懂, 而且他很會說故事 :D
Lance Fortnow, The Golden Ticket: P, NP, and the Search for the Impossible.
http://www.amazon.com/The-Golden-Ticket-Search-Impossible/dp/0691156492
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 101.10.74.15
推 LCamel :推這篇 06/02 23:01
推 suhorng :借轉！ 06/02 23:59
推 Chatterly :推好文 06/03 01:51
推 WINDHEAD : 06/03 03:00
推 gj942l41l4 :推 06/03 03:08
推 Scape :謝謝LPH66 id010406 hcsoso及其他幾位版友 06/03 13:12
→ Scape :一直搞不清楚什麼是NP完備問題，現在有些初步概念了 06/03 13:13
推 TassTW :推推 06/03 17:05
→ hcsoso :請自由轉文喔~ 06/03 21:13
→ kaifrankwind:想請問一下:為什麼P=NP的話 數學證明就可以自動化了? 06/03 23:01
→ hcsoso :因為 "給定一個定理敘述, 證明該定理" 是個 NPC 問題 06/03 23:31
→ hcsoso :因此 P = NP 的話, 就會有個多項式時間演算法可以找 06/03 23:32
→ hcsoso :證明. 06/03 23:34
→ hcsoso :當然, 如果是個很差的多項式那就不能真的去跑程式了, 06/03 23:35
→ hcsoso :所以只能說"理論上"我們就有自動化的方法可以作數學. 06/03 23:36
→ hcsoso :這也是我不相信 P = NP 的理由之一 :P 06/03 23:37
推 plover :有誰想要驗證paper的，快點炸一個反例 XD 06/04 23:52
推 Hseuler :"證明自動化"這件事怪怪的 例如一階算術不存在 06/05 14:05
→ Hseuler :recursively enumerable公理系統 06/05 14:06
→ Hseuler :所以普遍的自動定理證明器是不可能的 06/05 14:07
推 Hseuler :(上面指的是完備且無矛盾的的r.e. set ) 06/05 14:38
→ hcsoso :的確，我上面那段話是蠻不負責的，因為我跟邏輯不太 06/05 21:21
→ hcsoso :熟... 樓樓上可以多講一點嗎 06/05 21:23
→ hcsoso :因為我印象中 {(P,1^n) | 定理 P 在 ZF 系統中有長度 06/05 22:37
→ hcsoso :最多 n 的證明} 這個 language 是 NP-complete. 06/05 22:38