作者XrGodz (纽爱铜管分部首席)
看板TransCSI
标题Re: [问题]关於Polynomial time solution~
时间Thu Jun 14 23:38:37 2007
※ 引述《antirazin (你今天督了吗XD)》之铭言：
: ※ 引述《librayan926 (YAN)》之铭言：
: : polynomial time can solve problem that is a polynmial problem
: : P Problem the same polynomial problem
: : just like contest time better than polynomial time.
: : the exponential time solution is better then polynomial time
: : solution absolutely.
: : yes, turing machine is a dream machine
: : offer a model to research limit of computational process
: 下列哪一个是正确的？
: (1)A problem that has a polynomial time solution can always be solved in
: a practical amount of time
: (2)A polynomial is also an NP problem
: (3)A non-polynomial problem is called an NP problem
答案是3...
NP就是 non-polynomial...
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 218.160.185.123
1F：→ XrGodz:这题是台联大考的吧...... 06/14 23:39
2F：→ XrGodz:跑去问老师...他一直在讦诮怎麽会出这种题目= = 06/14 23:39
3F：推 antirazin:嗯嗯~我问老师他说出这种题目分数送它XD 06/14 23:50
4F：→ antirazin:不过我有疑问的是P是包含於NP里面吧，那麽(2)应也对吧 06/14 23:52
5F：→ antirazin:我去问老师，他这样跟我讲：给一个多项式问题，如果 06/14 23:54
6F：→ antirazin:以deterministic决定，则他是个P问题，反之以 06/14 23:54
7F：→ antirazin:non-deterministic去猜测，则是NP问题 06/14 23:55
8F：→ XrGodz:2)不对喔... 答案里面有"also".... 错= = 06/14 23:55
9F：→ XrGodz:老爱玩文字游戏....真xx!! 06/14 23:57
10F：推 antirazin:喔喔喔喔！！！！我懂你意思了 ＝ ＝＂ 题目真机 06/15 00:32
11F：推 x0315b100:囧... 06/15 10:50