若P不等于NP，则最大独立集问题存在多项式时间绝对近似算法。

第1题：

第2题：

第3题：

第4题：

设A，B为两个事件，以下哪些表述是不正确的（）。

• A、若A，B相互包含，则P(A∪B)=P(A)+P(B)
• B、若A，B互不相容，则P(A∪B)=P(A)+P(B)
• C、若A，B相互独立，则P(AB)=P(A)·P(B)
• D、若A，B互不相容，则P(AB)=P(A)P(B)
• E、若A，B相互独立，则P(B

正确答案:A,D

第5题：

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

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

第6题：

两个本原多项式g（x）和f（x），令h（x）=g（x）f（x）记作Cs，若h（x）不是本原多项式，则存在p当满足什么条件时使得p|Cs（s=0，1…）成立？（）

• A、p是奇数
• B、p是偶数
• C、p是合数
• D、p是素数

正确答案:D

第7题：

设P（A）=0.4，P（A+B）=0.7，若事件A与B互斥，则P（B）=（）；若事件A与B独立，则P（B）=（）.

正确答案:0.3；0.5

第8题：

邮递员问题，或者叫做最短路径问题是（）。

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

正确答案:B

第9题：

NP类语言在图灵机下的定义为（）

• A、NP={L∣L是一个能在非多项式时间内被一台NDTM所接受的语言}
• B、NP={L∣L是一个能在非多项式时间内被一台DTM所接受的语言}
• C、NP={L∣L是一个能在多项式时间内被一台DTM所接受的语言}
• D、NP={L∣L是一个能在多项式时间内被一台NDTM所接受的语言}

正确答案:D

第10题：

第11题：

第12题：

第13题：

第14题：

第15题：

第16题：

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

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

正确答案:A

第17题：

下面关于NP问题说法正确的是（）

• A、NP问题都是不可能解决的问题
• B、P类问题包含在NP类问题中
• C、NP完全问题是P类问题的子集
• D、NP类问题包含在P类问题中

正确答案:B

第18题：

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

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

第19题：

若p（x）是F（x）中次数大于0的多项式，则类比素数的观点不可约多项式有多少条命题是等价的？（）

• A、6.0
• B、5.0
• C、4.0
• D、3.0

正确答案:C

第20题：

排序问题是属于（）。

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

正确答案:A

第21题：

何谓P、NP、NPC问题？

正确答案: 1.P（Polynomial问题）：也即是多项式复杂程度的问题。
2.NP就是Non-deterministic Polynomial的问题，也即是多项式复杂程度的非确定性问题。
3.NPC（NP Complete）问题，这种问题只有把解域里面的所有可能都穷举了之后才能得出答案，这样的问题是NP里面最难的问题，这种问题就是NPC问题。

第22题：

第23题：

第24题：