Re: [問題]關於Polynomial time solution~
※ 引述《antirazin (你今天督了嗎XD)》之銘言：
: 後來我又和同學討論起這一題，
: 在此另外提出我的新問題，
: 1. 第一個選項看起來也是對的ㄚ～為何不選
: 2. 關於第二個選項，我覺得他開頭就定義錯誤了，
: 所謂的Ｐ問題，指的是該問題以多項式時間解決，
: 而不是在於該問題的形式是否為多項式問題，
: 所以從一開始，ＮＰ問題和多項式形式問題是沒有絕對關聯的
: 3. 如果上述成立，非多項式問題跟Ｐ或ＮＰ的問題無關，
: 因為NP = non-deterministic polynomial time，
: 換言之，是用一個非決定性的方式去檢測該問題的時間複雜度有多項式時間解。
: 重點是在是否為決定性測試去決定是否為NP或P問題!!
: 問題用決定性方法檢測出多項式時間解稱為P問題
: 問題用非決定性方法則就算找出多項式時間解，也不能斷定該問題為P，
: 因為非決定性方法的範圍較小，不具說服力，不能以此以偏概全，
: 所以用NP來涵蓋之
: 所以我選的答案是(1)
: 這題主要是邏輯問題~= ="
原題目:
Which of the following statements is ture for time complexity?
(1) A polynomial time solution to a problem is always better than an
exponential time solution.
(2) A problem that has a polynomial time solution can always be solved
in a practical amount of time.
(3) A polynomial problem is also an NP problem.
(4) A non-polynomial problem is called an NP problem.
(個人認為..)
1) 說多項式時間比指數時間來的好!!
這是不一定的，所以錯
2) 多項式時間的問題總是能被practical amount of time 解決!!
查不到practical amount of time正確的意思...但覺得是錯的
3) 從字面上翻譯:一個多項式問題也是非多項式問題
單純的認為是錯的...因為也有例外
4) 若是別想太多的話，這個選項是最漂亮的!!
PS. 我去問的老師有提到說
這個問題是從某本原文書上抄下來的
正常不會這樣出= ="
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.229.9.36
推
06/17 00:54, , 1F
06/17 00:54, 1F
推
06/17 18:09, , 2F
06/17 18:09, 2F
推
06/18 22:16, , 3F
06/18 22:16, 3F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 6 之 6 篇)：