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