※ 引述《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