1、如果一个决策问题可以在确定性图灵机上用时间复杂度为多项式函数𝑛^𝑘（其中n是输入大小，k是一个常数）解决，则该问题属于______类。

参考答案：P
解析：P类定义为那些存在多项式时间算法解决方案的问题。这个填空题测试了对P类基本定义的理解，
即能否识别出多项式时间复杂度是判定一个问题是否属于P类的关键标准。

2、判定一个问题是否属于P类的关键是看能否找到一个 ______ 算法来解决它。
参考答案: 多项式时间
解析: P类问题的定义是存在一个多项式时间算法可以解决的判定问题。关键在于算法的时间复杂度是多项式级的,而不是指数级或更高。

1、证明: 如果问题A可以在多项式时间内归约到问题B,且B属于P类,那么A也属于P类。
参考答案和解析:
证明:

1、假设问题A可以在多项式时间内归约到问题B,即存在一个多项式时间归约函数f,
使得对于任意输入x,x是A的实例当且仅当f(x)是B的实例。
2、又因为B属于P类,所以存在一个多项式时间算法来解决B。设这个算法为AlgB。
3、我们可以构造一个解决A的算法AlgA如下:

对于输入x,先用归约函数f将x转化为f(x)
然后用AlgB解决f(x)
返回AlgB的结果

4、AlgA的运行时间 = f的运行时间 + AlgB的运行时间
因为f和AlgB都是多项式时间的,所以它们的和仍然是多项式时间的。
5、因此,我们找到了一个解决A的多项式时间算法AlgA。

根据P类的定义,A属于P类。证毕。

1、考虑以下两个问题:
问题1: 给定一个n个顶点的无向图G和一个整数k,判断G是否存在一个大小为k的团(即k个顶点两两相连)。
问题2: 给定一个n个顶点的无向图G和一个整数k,判断G是否存在一个大小为k的独立集(即k个顶点两两不相连)。
(a) 请说明这两个问题之间的关系。
(b) 如果问题1属于P类,能否推断出问题2也属于P类?请证明你的结论。

参考答案和解析:
(a) 这两个问题是互补的。在一个图G中寻找大小为k的团,等价于在G的补图中寻找大小为k的独立集。
(b) 是的,如果问题1属于P类,那么问题2也属于P类。证明如下:

1、假设问题1属于P类,即存在一个多项式时间算法A来解决团问题。
2、对于问题2的任意输入(G, k),我们可以构造一个算法B如下:

计算G的补图G'。这可以在O(n^2)时间内完成,其中n是顶点数。
使用算法A判断G'是否存在大小为k的团。
返回A的结果。

3、算法B的正确性:
G中存在大小为k的独立集 <=> G'中存在大小为k的团
4、算法B的时间复杂度:

计算补图的时间 O(n^2)

运行算法A的时间 (多项式时间)
= 多项式时间

5、因此,我们找到了一个解决问题2的多项式时间算法B。

根据P类的定义,问题2属于P类。证毕。