作者TonyQ (骨頭)
看板Prob_Solve
標題Re: [問題] 請問有關P,NP,NP-HARD
時間Thu Nov 29 15:10:02 2007
※ 引述《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
1F：推 march20:算好懂, 直接跳掉 Turing Machine 的定義... 11/29 17:19
2F：推 LPH66:而且從來NP就不是Non-Polynomial... 11/29 18:42
3F：→ LPH66:它是Nondeterministic Polynomial 只是因為Nondeterministic 11/29 18:43
4F：→ LPH66:的性質才會造成它變成指數時間... 11/29 18:43
5F：推 dh3014:網站上是寫 nondeterministic polynomial 沒錯 11/30 08:15
6F：推 march20:NP 的問題不一定要是指數時間啊 XD 11/30 12:36
7F：推 march20:P 是 NP 的子集, 所以不能把指數時間當成是 NP 的必要條件 11/30 12:39
8F：推 march20:更何況, 如果哪天找到了某個 NP 問題是 EXP-TIME 11/30 12:40
9F：推 march20:那就等於證明了 NP != P 了, 那就厲害了 11/30 12:41
10F：推 march20:無論如何, 跟剛學 complexity 的人提到 P 或 NP, 千萬不要 11/30 12:41
11F：推 march20:講到任何指數時間的事, 那只會讓人更搞不清楚 @@ 11/30 12:42
12F：推 march20:(註: NP!=P 還沒有任何的證明或反證, 所以對於任何一個 NP 11/30 12:44
13F：推 march20:問題, 就算真的屬於 EXP-TIME, 目前一定還找不到證明...) 11/30 12:46
14F：→ TonyQ:話說我在上演算法的時候也是差不多是跳過圖靈機的定義XD 11/30 17:50