※ 引述《XrGodz (紐愛銅管分部首席)》之銘言：
: ※ 引述《antirazin (你今天督了嗎XD)》之銘言：
: : 下列哪一個是正確的？
: : (1)A problem that has a polynomial time solution can always be solved in
: : a practical amount of time
: : (2)A polynomial problem is also an NP problem
: : (3)A non-polynomial problem is called an NP problem
: 答案是3...
: NP就是 non-polynomial...
後來我又和同學討論起這一題，
在此另外提出我的新問題，
1. 第一個選項看起來也是對的ㄚ～為何不選
2. 關於第二個選項，我覺得他開頭就定義錯誤了，
所謂的Ｐ問題，指的是該問題以多項式時間解決，
而不是在於該問題的形式是否為多項式問題，
所以從一開始，ＮＰ問題和多項式形式問題是沒有絕對關聯的
3. 如果上述成立，非多項式問題跟Ｐ或ＮＰ的問題無關，
因為NP = non-deterministic polynomial time，
換言之，是用一個非決定性的方式去檢測該問題的時間複雜度有多項式時間解。
重點是在是否為決定性測試去決定是否為NP或P問題!!
問題用決定性方法檢測出多項式時間解稱為P問題
問題用非決定性方法則就算找出多項式時間解，也不能斷定該問題為P，
因為非決定性方法的範圍較小，不具說服力，不能以此以偏概全，
所以用NP來涵蓋之
所以我選的答案是(1)
這題主要是邏輯問題~= ="
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 219.68.64.202