题目内容
（请给出正确答案）
[主观题]
多项式时间
所有可以在多项式时间内解决的确定性问题是()
A、确定性问题
B、P类复杂问题
C、NP类复杂问题
D、Co-NP类复杂问题
提问人：网友fanweik
发布时间：2022-01-07
如搜索结果不匹配，请 
A.确定性问题
B.P类复杂问题
C.NP类复杂问题
D.Co-NP类复杂问题
题目内容
（请给出正确答案）
您可能会需要：
安装简答题APP，拍照搜题省时又省心！
更多“多项式时间”相关的问题
第4题
在计算复杂性理论中，将所有可以在多项式时间内求解的问题称为 ，而将所有在多项式时间内可以验证的问题称为 。 （）
A.P类问题、NP类问题
B.NP类问题、P类问题
C.NP-C问题、P类问题
D.NP类问题、NP-C问题
第5题
在计算复杂性理论中，将所有可以在多项式时间内求解的问题称为 ，而将所有在多项式时间内可以验证的问题称为 。例如“证比求易算法”。
A.P类问题、NP类问题
B.NP类问题、P类问题
C.NP-C问题、P类问题
D.NP类问题、NP-C问题
第6题
在“证比求易算法”中，对公主给出的数进行验证，显然是在多项式时间内可以解决的问题，因此，这类问题属于NP类问题。现在，P=NP是否成立的问题是计算学科和当代数学研究中最大的悬而未决的问题之一。2000年5月，美国克莱数学研究所（The Clay Institute of Mathematics）提供100万美元求解这一问题。下面论述错误的是（）
A、库克（S. A. Cook）等人认为NP类中的某些问题的复杂性与整个类的复杂性有关，当这些问题中的任何一个存在多项式时间算法时，所有NP问题都是在多项式时间内可解的，这些问题被称为NP完全性问题。
B、库克因其在计算复杂性理论方面（主要是在NP完全性理论方面）的奠基性工作，于1982年获ACM图灵奖。
C、历史上第一个NP完全性问题是库克于1971年提出的可满足性问题。
D、若P≠NP，则所有在多项式时间内可验证的问题都将是在多项式时间内可求解（或可判定）的问题。
第7题
可解性问题是指能够找到多项式时间复杂性算法进行求解的问题，难解性问题是指找不到多项式时间复杂性算法进行求解的问题。下列说法不正确的是_____。
A.P类问题是可解性问题，NP类问题是难解性问题
B.NP类问题不一定是难解性问题，因为P类问题也一定是NP类问题
C.NP类问题不确定是否是P类问题，但NPC类问题一定是难解性问题
D.上述说法有不正确的
第8题
可解性问题是指能够找到多项式时间复杂性算法进行求解的问题，难解性问题是指找不到多项式时间复杂性算法进行求解的问题。下列说法不正确的是_____。
A.P类问题是可解性问题，NP类问题是难解性问题
B.NP类问题不一定是难解性问题，因为P类问题也一定是NP类问题
C.NP类问题不确定是否是P类问题，但NPC类问题一定是难解性问题
D.其他三个选项的说法有不正确的
第9题
P类问题、NP类问题、NPC类问题是计算机科学领域关于可求解性可计算性很重要的概念。关于P、NP和NPC类问题，可解性问题是指能够找到多项式时间复杂性算法进行求解的问题，难解性问题是指找不到多项式时间复杂性算法进行求解的问题。下列说法不正确的是_____
A.P类问题是可解性问题，NP类问题是难解性问题
B.NP类问题不一定是难解性问题，因为P类问题也一定是NP类问题
C.NP类问题不确定是否是P类问题，但NPC类问题一定是难解性问题
D.其他三个选项的说法有不正确的
