作者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