第10章-问题的复杂性.pptVIP

第10章_问题的复杂性;计算的限制;不可解问题UnsolubleProblem

难解问题虽没找到多项式时间算法，但按指数时间算法的难解问题至少在理论上可以用计算机求解。

但有些问题不论耗多少时间也不能用计算机求解。

不能用计算机求解（不论耗费多少时间）的问题称为不可解问题

;例：不可解问题典型例子：停机问题（haltingproblem）

;判定问题DecisionProblem

判定问题是仅仅要求回答“yes”或“no”的问题。

很多实际问题可以转化为一系列更容易研究的判定问题。举例如下：;例1：排序问题

排序问题的判定形式可叙述为：

给定一个整数数组，是否可以按非降序排列

例2：图着色问题

图着色问题的判定形式可叙述为：

给定无向连通图G=（V，E）和一个正整数k，是否可以用k种颜色为G中所有顶点着色，使得任何两个相邻顶点着色不同。

例3：TSP问题

TSP问题的判定形式可叙述为：;给定一个带权图G=（V，E）和一个正整数k，是否有一个经过所有顶点一次且仅一次再回到出发点的回路，其总距离小于k。

例4：哈密顿回路问题

哈密顿回路问题的判定形式可叙述为：

在图G=（V，E）中，是否有一个回路经过所有顶点一次且仅一次再回到出发点。

判定问题的重要特性——验证比求易;即在计算上对问题求解是困难的，但在计算上判定一个待定解是否解决了该问题却是简单的。

例1：求“哈密顿回路问题”是难解问题

但验证一个给定顶点序列是不是“哈密顿回路”却很容易，即只需要检查前n个顶点是否互不相同，而最后一个顶点与第一个顶点是否相同

例2：求大整数S=49770428644836899的因子是个难问题

但要验证a=223092871是不是大整数S的因子却很容易。只要将S除以这个因子，余数为0即可;例3：求线性方程组的解可能很困难，

但验证一组解是否是方程组的解却很容易，只要将这组解代入方程组中，然后验证是否满足这组方程即可。

确定性算法与P类问题

定义2.1设A是求解问题Π的一个算法，如果在算法的整个执行过程中，每一步只有一个确定的选择，并且对于同一输入实例运行算法，所得的结果严格一致，则称算法A是确定性（Determinism）算法。;定义2.2如果对于某个判定问题Π，存在一个非负整数k，对于输入规模为n的实例，能够以O(nk)的时间运行一个确定性算法，得到yes或no的答案，则该判定问题Π是一个P类（Polynomial）问题。;猜测阶段

在这个阶段，对问题的输入实例产生一个任意字符串y，在算法的每一次运行时，串y的值可能不同，因此，猜测以一种非确定的形式工作。

验证阶段

在这个阶段，用一个确定性算法验证：

①检查在猜测阶段产生的串y是否是合适的形式，如果不是，则算法停下来并得到no；

②如果串y是合适的形式，则验证它是否是问题的解，如果是，则算法停下来并得到yes，否则算法停下来并得到no。;定义2.4如果对于某个判定问题Π，存在一个非负整数k，对于输入规模为n的实例，能够以O(nk)的时间运行一个非确定性算法，得到yes或no的答案，则该判定问题Π是一个NP类（NondeterministicPolynomial）问题。;P类问题和NP类问题的主要差别：

P类问题可以用多项式时间的确定性算法来进行判定或求解；

NP类问题可以用多项式时间的非确定性算法来进行判定或求解。

如果问题Π属于P类，则存在一个多项式时间的确定性算法来判定和求解，显然，也可以构造一个多项式时间的非确定性算法来验证其解的正确性，因些问题Π也属于NP类，即

但如果问题Π属于NP类，则存在一个多项式时间的非确定性算法来猜测与验证它的解，但不一定能构造一个多项式时间的确定性算法来判断和求解。即;NP完全问题;问题变换;问题变换的一般过程;问题变换意义

若在的时间内完成上述输入和输出转换，则称问题以时间变换到问题，记为：

其中，n为问题规模；

若在多项式时间内完成上述输入和输出转换，则称问题以多项式时间变换到问题，记为：;排序问题——输入I是一组整数X=(x1,x2,…,xn)，输出O是这组整数的一个排列xi1≤xi2≤…≤xin。

配对问题——输入I是两组整数X=(x1,x2,…,xn)和Y=(y1,y2,…,yn)，输出O是两组整数的元素配对，即X中的最小值与Y中的最小值配对，X中的次小值与Y中的次小值配对，依此类推。;;注：问题变换的主要目的不是给出解决一个问题的算法，而是给出通过另一个问题理解一个问题的计算时间上下限