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