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

[TonyQ (骨頭)]

※ 引述《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
推 march20:算好懂, 直接跳掉 Turing Machine 的定義...
推 LPH66:而且從來NP就不是Non-Polynomial...
→ LPH66:它是Nondeterministic Polynomial 只是因為Nondeterministic
→ LPH66:的性質才會造成它變成指數時間...
推 dh3014:網站上是寫 nondeterministic polynomial 沒錯
推 march20:NP 的問題不一定要是指數時間啊 XD
推 march20:P 是 NP 的子集, 所以不能把指數時間當成是 NP 的必要條件
推 march20:更何況, 如果哪天找到了某個 NP 問題是 EXP-TIME
推 march20:那就等於證明了 NP != P 了, 那就厲害了
推 march20:無論如何, 跟剛學 complexity 的人提到 P 或 NP, 千萬不要
推 march20:講到任何指數時間的事, 那只會讓人更搞不清楚 @@
推 march20:(註: NP!=P 還沒有任何的證明或反證, 所以對於任何一個 NP
推 march20:問題, 就算真的屬於 EXP-TIME, 目前一定還找不到證明...)
→ TonyQ:話說我在上演算法的時候也是差不多是跳過圖靈機的定義XD