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