第9章怎样研究算法:遗传算法示例
1、P类问题、NP类问题、NPC类问题是计算机科学领域关于可求解性可计算性很重要的概念。 关
于P、NP和NPC类问题，回答下列问题。
(1) ___________________ 下列说法不正确的是 o
(A) P类问题是计算机可以在冇限时间内能够求解的问题；
(B) NP类问题是计算机可以在有限时间内能够验证“解”的正确性的问题;
(C) NPC类问题是对问题的每一个可能解，计算机都可以在有限时间内验证“解”的正确性 的
问题，被称为NP完全问题；
(D) 上述说法有不正确的;
答案：D 解释：
本题考核P类问题、NP类问题、NPC类问题的概念。
P类问题指计算机可以在有限时间内求解的问题，(A)正确；NP类问题指虽然在多项式时间 内
难于求解但不难判断给定一个解的正确性问题,(B)正确；NPC问题指NP问题的所有可能答案 都可以在多项式时间内进行正确与否的验算，称为NP-Complete问题,(C)正确;(A)(B)(C)都正确， 所以
(D)错误。
具体内容请参考第九章视频之“可求解与难求解问题”以及第九章课件。
(2) _____________________________________________ 可解性问题是指能够找到多项式时
间复杂性算法进行求解的问题，难解性问题是指找不到多项 式时间复杂性算法进行求解的问题。下列说法不正确的是 _________________________________________ 。
(A) P类问题是可解性问题，NP类问题是难解性问题。
(B) NP类问题不一?定是难解性问题，因为P类问题也定是NP类问题； (C) NP类问题不确定是否是P类问题，但NPC类问题-淀是难解性问题； (D) 上述说法有不正确的；
答案：A 解释：
本题考核对可解性问题和难解性问题概念的理解。
P类问题指计算机町以在冇限时间内求解的问题，所以是可解性问题；NP类问题指虽然在多 项
式时间内难于求解但不难判断给定一个解的正确性问题，但P类问题是NP类问题的一个了集， 所以
NP类问题不…定是难解性问题；NPC问题指NP问题的所仃可能答案都可以在多项式时间
内进行正确与否的验算，称为NP-Complete问题，是难解性问题，综上(A)错误。 具体内容请参考第
九章视频之“可求解与难求解问题”以及第九章课件。
(3) _________________ 下列说法正确的 o
(A) P类问题是计算机可以在有限时间内能够求解的问题； (B) NP类问题是计算机可以在有限时间内能够求解的问题； (C) NPC类问题是计算机可以在有限时间内能够求解的问题; (D) 上述说法都正确;
答案：A 解释：
本题考核P类问题、NP类问题、NPC类问题的概念。
只有P类问题是计算机可以在有限时间内能够求解的问题，所以(A)正确。 具体内容请参考第九讲视频之“可求解与难求解问题”以及第九章课件。
(4) ________________________________________________ P类问题是多项式问题(Polynomial Problem), NP类问题是 _____________________________ 。
(A) 非多项式问题； (B) 非确定性多项式问题； (C) 非P类问题； (D) 确定性非多项式问题; (E) 上述说法都正确；
答案：B 解释：
本题考核对NP类问题的理解。
P类问题是多项式问题(Polynomial Problem), NP类问题是非确定性多项式问题 (Non-deterministic
Polynomial), NPC问题是完全非确定性多项式问题(NP-Complete),所以(B)正确。
具体内容请参考第九章视频Z “可求解与难求解问题”以及第九章课件。
(5) ___________________ 下列说法不正确的 o
(A) P类问题是总能找到一个多项式时间复杂性算法进行求解的问题； (B) NP类问题是一定找不到多项式时间复杂性算法进行求解的问题； (C) NP类问题是不确定能够找到多项式时间复朵性算法进行求解的问题；
(D) NP类问题虽然是不确定能找到多项式时间复杂性算法进行求解，但一定能找到多项式时 间
复杂性算法进行“解”的正确性验证的问题；
(E) 上述说法有不正确的；
第9章怎样研究算法遗传算法示例练习题答案解析.docx
