PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

Re: [問題] 請問有關P,NP,NP-HARD

看板Prob_Solve (計算數學 Problem Solving)作者 (骨頭)時間17年前 (2007/11/29 15:10), 編輯推噓11(11推 0噓 3→)
留言14則, 4人參與, 最新討論串2/2 (看更多)
※ 引述《ifye (if)》之銘言： : 大家好~ : 小弟對於NP-HARD有些問題不懂, : 所以上來請教大家, : 分別是: 其實我之前是參考這個網站的資料 http://episte.math.ntu.edu.tw/articles/mm/mm_10_2_04/ 我覺得它寫的算好懂 參考看看:P -- 這些問題真是詭異 XD -- 　▄▅▆▇███▇▆▅▄▃　　　　　　　　╰┼╯─╮ ╮　　　　　 　 　◥███████████◣　　　　　　　╰┼╯＝│=│　　　　　　　　 ◥██████───────◣　　　　＊．　╯　 ╯ ╯ の　物　語　．＊ 　◥███████──────◣　～　◢◣　　　　　　　　　　　　 ◢◣ 　◥██████───────◤　　　◥◤＊　　空白的世界．翼 ＊◥◤ 　◥██▁▂▃▄▅▆▇███▆▅▄▃▂▂～telnet://tony1223.no-ip.info -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 220.132.59.247
推
11/29 17:19, , 1F
算好懂, 直接跳掉 Turing Machine 的定義...
11/29 17:19, 1F
推
11/29 18:42, , 2F
而且從來NP就不是Non-Polynomial...
11/29 18:42, 2F
→
11/29 18:43, , 3F
它是Nondeterministic Polynomial 只是因為Nondeterministic
11/29 18:43, 3F
→
11/29 18:43, , 4F
的性質才會造成它變成指數時間...
11/29 18:43, 4F
推
11/30 08:15, , 5F
網站上是寫 nondeterministic polynomial 沒錯
11/30 08:15, 5F
推
11/30 12:36, , 6F
NP 的問題不一定要是指數時間啊 XD
11/30 12:36, 6F
推
11/30 12:39, , 7F
P 是 NP 的子集, 所以不能把指數時間當成是 NP 的必要條件
11/30 12:39, 7F
推
11/30 12:40, , 8F
更何況, 如果哪天找到了某個 NP 問題是 EXP-TIME
11/30 12:40, 8F
推
11/30 12:41, , 9F
那就等於證明了 NP != P 了, 那就厲害了
11/30 12:41, 9F
推
11/30 12:41, , 10F
無論如何, 跟剛學 complexity 的人提到 P 或 NP, 千萬不要
11/30 12:41, 10F
推
11/30 12:42, , 11F
講到任何指數時間的事, 那只會讓人更搞不清楚 @@
11/30 12:42, 11F
推
11/30 12:44, , 12F
(註: NP!=P 還沒有任何的證明或反證, 所以對於任何一個 NP
11/30 12:44, 12F
推
11/30 12:46, , 13F
問題, 就算真的屬於 EXP-TIME, 目前一定還找不到證明...)
11/30 12:46, 13F
→
11/30 17:50, , 14F
話說我在上演算法的時候也是差不多是跳過圖靈機的定義XD
11/30 17:50, 14F
‣ 更多 TonyQ 的文章
文章代碼(AID): #17JcNCWM (Prob_Solve)
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 2 之 2 篇)：
排序： 最舊先 | 最新先 | 留言數
在新視窗開啟完整討論串 (共2篇)
Prob_Solve 近期熱門文章
更多 近期熱門文章 >>
PTT數位生活區 即時熱門文章
更多 即時熱門文章 >>
‣ 更多 TonyQ 的文章
文章代碼(AID): #17JcNCWM (Prob_Solve)