作者LPH66 (-858993460)
看板CSSE
標題Re: [問題] P=NP是什麼？
時間Tue Sep 20 12:44:28 2011
※ 引述《mabus (CodeINCEPTION)》之銘言：
: 能不能用白話一點的方式解釋？在wiki裡有看沒懂呀...。
: 若這個問題解決了，有什麼影響嗎？
: 本身不是學CS的，可以的話能否推薦書籍呢？
: 先謝謝各位了！
這個大概沒什麼書會討論吧...
你說你不是學 CS 的那這篇就儘量不放太多專有名詞進去
P = NP 的意義是這樣的
我們現在有一類問題叫做 P 有另一類問題叫做 NP
P 的問題就是解決它所需時間隨著問題大小只成多項式成長
(例如問題大小的三次方或五次方成長等等)
NP 的問題就是給我問題和一個答案我可以很快的檢查這是不是真的是這問題的答案
(同樣這裡的很快是指多項式成長)
P = NP 問題就是問說這兩類問題到底是不是一樣的
之所以這是難題的原因是 NP 裡有一大類問題被叫做 NP-Complete (NP完全)
目前最好的解法所需要的時間都隨著問題大小增加而成指數成長
找不到多項式成長的解法 但也無法證明它不存在這種解法
這代表當我們想要解決一個稍微大一點的問題時目前暫時沒有很快的解法存在
以其中一個問題 旅行推銷員問題 為例
它需要我們在一張地圖上找出經過所有城市正好一次再回到出發點的最短路線
最簡單的想法就是所有路線都去試試看 那試的次數就是城市數的階乘
用一些技巧可以把試的次數降到指數成長
但是目前仍然找不到多項式成長的做法 也證明不出不存在這種做法
雖然 P = NP 是個很大的問題 但是看起來又好像沒有那麼難
這是因為所有的 NP-Complete 問題有種一個串一個的性質就是
如果你找到其中一個問題的多項式成長做法之後
你可以一個串一個地給出所有 NP-Complete 問題的多項式成長做法
最後再串到所有 NP 問題也都能給出多項式成長做法
於是你就證明了 P = NP
反過來如果你證明了其中一個問題不能有這種做法的話
那麼你便找到了一個問題是屬於 NP 但不屬於 P 的 於是證明了 P≠NP
無論哪一個你都會在歷史上留名的 (附帶一筆一百萬鎂的獎金 XD)
之所以現在許多計算機理論家會這麼想要解決它也是因為 NP-Complete 問題實在很多
英文維基上就列出了至少一兩百個屬於 NP-Complete 的問題
去年的這個時候也有一個叫 Vinay Deolalikar 的傢伙提出了可能是 P≠NP 的證明
(後來被其他專家挑出幾個重大錯誤 他現在還在改)
影響的話其實個人認為剛證出來時多半是理論上的影響
畢竟它要的是多項式成長 如果是以問題大小的一百次方成長也算
但一百次方實際上很難有什麼實質上的影響
但當更進一步的研究之後
NP-Complete 問題這種一個串一個的性質很容易發生某處一個小進步就擴展到全部
這時一些依靠這些問題這種強度的使用就變得不可靠了
例如最常提的就是密碼學上的應用 若 P = NP 被證明之後許多這些應用都會變得不安全
(像是這裡面最常提的 RSA 所依靠的質因數分解
這個問題目前只已知是 NP 連是不是 NP-Complete 都不知道
但如果 P = NP 被證明的話它一樣會遭殃)
反過來如果證明了 P≠NP 那我們可以放心的說這些問題要完美解決沒招
於是可以專心的研究它們的近似演算法 (就是能給出接近完美的做法 這可以快很多)
這方面的研究現在就已經很多了
(因為現在許多狀況證據都讓大家認為 P≠NP 應該是對的
所以與其去撞這堵大牆不如先去做一些能夠做的實質性進展)
--
嘛我知道這篇文章稍微用點嚴格的方式來挑可以有一堆毛病啦
(像是 NP-Complete 的定義性質 以及我故意完全不提 co-NP 和 NP-hard 等等)
不過看在這是篇給外行人看的文章就先這樣就好...
--
'Oh, Harry, don't you
see?' Hermione breathed. 'If she could have done
one thing to make
absolutely sure that every single person in this school
will read your interview, it was
banning it!'
---'Harry Potter and the order of the phoenix', P513
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.28.92
推 mabus:如果這個方法實現了，是不是可以預知未來呀？ 09/20 12:51
→ mabus:這是不是像翻書一樣呀？要翻到指定的那一頁，總要試幾次， 09/20 12:53
→ mabus:若是這個方法實現了，那每次翻都可以翻到指定頁面？ 09/20 12:54
→ mabus:又或者明天會發生什麼事，過去就可以事先知道？ 09/20 12:54
→ mabus:可是，有沒有具體一點的例子？像是這個方法實現了，就可以讓 09/20 12:56
→ mabus:單核心的處理器發揮出N核心的的效能？ 09/20 12:56
→ LPH66:沒有到預知未來這麼誇張啦 只是可以快"很多"而已 09/20 12:57
→ mabus:啊，我又異想天開了...。 09/20 12:57
→ LPH66:這個"很多"是多項式成長和指數成長的差別 09/20 12:57
→ LPH66:具體一點的例子就像我文中說的 RSA 啊 09/20 12:58
推 mabus:也就是說，目前的安全，是基於慢很多的條件下才成立的呀。 09/20 13:00
→ LPH66:P=NP 若證明→質因數分解可以"很快"→ RSA 危險了 09/20 13:00
→ LPH66:大概像這種感覺 你沒說錯 很多現代密碼學的東西都是這樣 09/20 13:01
→ LPH66:幾乎沒有 impossible 只有 infeasible 09/20 13:02
推 mabus:那這個方法、理論，是建立在已經存在的事物上囉？ 09/20 13:03
→ mabus:並非可以去讓我用最小的消耗，去執行未知的事物。 09/20 13:04
→ mabus:像是讓電腦去預測我要做什麼，而不經由學習。 09/20 13:05
推 mabus:好像把趨近盡可能逼近的感覺呀。 09/20 13:08
推 yayarice:NP真的很難懂啊.... 09/20 17:33
推 vity:寫得不錯~可以再寫NP-Hard嗎 像halting problem 09/21 14:35
推 demintree:質因數分解還沒證明在NP中吧.... 09/21 21:03
→ bernachom:別人提出的證明，你真的很閒的話可以看一看 09/22 00:26
→ bernachom:我是說2012那篇，推錯了 09/22 00:26
→ azureblaze:前提是要能在O(1)內毀滅整個宇宙XD 09/24 22:13
→ LPH66:質因數分解是 NP 喔 因為給定分解我們可以乘起來看對不對 09/26 13:45
→ LPH66:這正符合"給定答案檢查對不對"的定義 09/26 13:45
→ LPH66:順帶一提, 在 AKS 出現之前它的確還沒證明在 NP 裡 09/26 13:54
→ LPH66:是在 AKS 出現後我們才能用多項式時間檢查給定的數真是質數 09/26 13:54
→ LPH66:因此 AKS 也連帶證明了質因數分解在 NP 09/26 13:55
→ LPH66:(以及co-NP, 如果你知道這是什麼的話) 09/26 13:55
→ shiuhungjr:質數的檢測已經被證明在P中，請google"prime is in p" 09/28 00:47
→ LPH66:那正是我提到的 AKS 09/28 14:10