請證明停機問題是NP-hard。 如果是"找一個NP-hard 問題去reduce 到它"的做法的話， 最好能附上若該問題為true，則reduce 到停機問題為true。 若reduce 到停機問題 ... ... <看更多>
np問題 在 np問題續約？ 的推薦與評價
np問題 續約？ - 想請問各位大大本來當初月租588配一隻手機現在遠傳問我要不要續約，合約到期了就每月599送無線藍芽耳機跟3m空氣清淨機二選一續約划算 ... ... <看更多>
np問題 在 NP-completeness Problem | Ldy's Blog 的推薦與評價
NP hard:NP难问题，所有NP问题在多项式时间内都能约化(Reducibility)到它的问题(不一定是NP问题)。 如果任何NP完全问题是可以多项式求解的，则P=NP， ... ... <看更多>
np問題 在 [問題] 合約到期請益- MobileComm - PTT情感投資事業版 的推薦與評價
合約即將到期， 只有使用網路， 聯絡都是用APP比較多， 網路使用成份較重， 其他功能的話還好， 我現在是中華的， NP台哥大688 30個月， 會折扣6300， ... ... <看更多>
np問題 在 Re: [問題] P=NP是什麼？ - 看板CSSE - 批踢踢實業坊 的推薦與評價
※ 引述《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
... <看更多>