下面关于NP问题说法正确的是()A、NP问题都是不可能解决的问题B、P类问题包含在NP类问题中C、NP完全问题是P类问题的子集D、NP类问题包含在P类问题中

题目

下面关于NP问题说法正确的是()

  • A、NP问题都是不可能解决的问题
  • B、P类问题包含在NP类问题中
  • C、NP完全问题是P类问题的子集
  • D、NP类问题包含在P类问题中
如果没有搜索结果或未解决您的问题,请直接 联系老师 获取答案。
相似问题和答案

第1题:

样本率p的正态近似条件为()。

A.np与n(1-p)≥5

B.np与n(1-p)≤5

C.np或n(1-p)≥5

D.np或n(1-p)≤5


正确答案:A

第2题:

若L是一个NP完全问题,L经过多项式时间变换后得到问题l,则l是()

  • A、P类问题
  • B、NP难问题
  • C、NP完全问题
  • D、P类语言

正确答案:A

第3题:

下面关于NP问题说法正确的是()

A.NP问题都是不可能解决的问题

B.P类问题包含在NP类问题中

C.NP完全问题是P类问题的子集

D.NP类问题包含在P类问题中


参考答案:B

第4题:

写出3个NP完全问题。


正确答案:团问题、子集和问题、旅行售货员问题。

第5题:

请列举几个常见的NP完全问题。


正确答案: 1)合取范式的可满足性问题;
2)三元合取范式的可满足性问题;
3)团问题;
4)顶点覆盖问题;
5)子集和问题;
6)哈密顿回路问题;
7)旅行售货员问题。

第6题:

满足下面()条件时,可以认为抽样成数的概率分布近似正态分布。

A.n≥30,np≥5,n(1-P)≥5
B.n≥30,np≤5,n(1-P)≤5
C.n≥30,np≥5,n(1-p)≤5
D.n≥30,np≤5,n(1-P)≥5

答案:A
解析:

第7题:

什么是P类问题?什么是NP类问题?请描述集合覆盖问题的近似算法的基本思想。


正确答案:用确定的图灵机可以在多项式实践内可解的判定问题称为P类问题。
用不确定的图灵机在多项式实践内可解的判定问题称为P类问题。
集合覆盖问题的近似算法采用贪心思想:对于问题,每次选择F中覆盖了尽可能多的未被覆盖元素的子集S,然后将U中被S覆盖的元素删除,并将S加入C中,最后得到的C就是近似最优解。

第8题:

NP类问题包含在P类问题中。()

此题为判断题(对,错)。


正确答案:×

第9题:

请解释什么是P问题,NP问题。


正确答案: 如果一个问题可以找到一个能在多项式的时间里解决它的算法,那么这个问题就属于P问题。P是英文单词多项式的第一个字母。
NP问题是指可以在多项式的时间里验证一个解的问题。NP问题的另一个定义是,可以在多项式的时间里猜出一个解的问题。

第10题:

排序问题是属于()。

  • A、P问题
  • B、NP问题
  • C、P和NP问题
  • D、以上都不是

正确答案:A