第2章第4节 wpf完全问题

《第2章第4节 wpf完全问题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第2章WPF完全理论2.4WPF完全问题2.4.1问题变换与计算复杂性归约2.4.2WPF完全问题的定义2.4.3基本的WPF完全问题2.4.4WPF完全问题的计算机处理2.4.1问题变换与计算复杂性归约定义2.5假设问题Π'存在一个算法A，对于问题Π'的输入实例I'，算法A求解问题Π'得到一个输出O'，另外一个问题Π的输入实例是I，对应于输入I，问题Π有一个输出O，则问题Π变换到问题Π'是一个三步的过程：1.输入转换：把问题Π的输入I转换为问题Π'的适当输入I'；2.问题求解：对问题Π'应用算法A产生一个输出O'；3.输出转换：

2、把问题Π'的输出O'转换为问题Π对应于输入I的正确输出。问题变换的一般过程问题Π问题Π' 算法AI输入转换I'O'O输出转换l问题变换的主要目的不是给出解决一个问题的算法，而是给出通过另一个问题理解一个问题的计算时间上下限的一种方式。例：配对问题到排序问题的变换排序问题——输入I'是一组整数X=(x1,x2,…,xn)，输出O'是这组整数的一个排列xi1≤xi2≤…≤xin。配对问题——输入I是两组整数X=(x1,x2,…,xn)和Y=(y1,y2,…,yn)，输出O是两组整数的元素配对，即X中的最小值与Y中的最小值配对，X中的次

3、小值与Y中的次小值配对，依此类推。配对问题到排序问题的变换过程假设存在算法A解决排序问题，则配对问题可以变换到排序问题：1．把配对问题的输入I转化为排序问题的两个输入I1'和I2'；2．排序这两组整数，即应用算法A对两个输入I1'和I2'分别排序得到两个有序序列O1'和O2'；3．把排序问题的输出O1'和O2'转化为配对问题的输出O，这可以通过配对每组整数的第一个元素、第二个元素、……来得到。l配对问题到排序问题的变换有助于建立配对问题代价的一个上限，因为上述输入和输出转换都是在多项式时间完成，所以，如果排序问题有多项式时间算法，

4、则配对问题也一定有多项式时间算法。定理2.2（计算时间下限归约）若已知问题Π的计算时间下限是T(n)，且问题Π可τ(n)变换到问题Π'，即Π∝τ(n)Π'，则T(n)－O(τ(n))为问题Π'的一个计算时间下限。定理2.3（计算时间上限归约）若已知问题Π'的计算时间上限是T(n)，且问题Π可τ(n)变换到问题Π'，即Π∝τ(n)Π'，则T(n)＋O(τ(n))为问题Π的一个计算时间上限。 计算时间下限归约：T(n)τ(n)T(n)－O(τ(n)) 计算时间上限归约：T(n)＋O(τ(n))τ(n)T(n)问题Π变换问题Π'

5、定理2.4设Π、Π'和Π''是三个判定问题，若Π∝pΠ'且Π'∝pΠ''，则Π∝pΠ''。l多项式时间复杂性具有闭包性。2.4.2WPF完全问题的定义定义2.6令Π是一个判定问题，如果问题Π属于WPF类问题，并且对WPF类问题中的每一个问题Π'，都有Π'∝pΠ，则称判定问题Π是一个WPF完全问题（WPFCompleteProblem），有时把WPF完全问题记为WPFC。NPF类问题NPF完全问题P＝WPF？广义上说，P类问题是可以用确定性算法在多项式时间内求解的一类问题，WPF类问题是可以用非确定性算法在多项式时间猜测并验证的一类

6、问题，而且P⊆WPF。目前人们猜测P≠WPF，则P类问题、WPF类问题、WPF完全问题之间的关系如下：NPF类问题P类问题NPFC问题定义2.7令Π是一个判定问题，如果对于WPF类问题中的每一个问题Π'，都有Π'∝pΠ，则称判定问题Π是一个WPF难问题。NPF类问题NPF难问题WPF完全问题和WPF难问题的区别：l如果Π是WPF完全问题，Π’是WPF难问题，那么，他们之间的差别在于Π必定是WPF类问题，而Π’不一定在WPF类问题中。一般而言，若判定问题属于WPF完全问题，则相应的最优化问题属于WPF难问题。2.4.3基本的WPF完

7、全问题证明一个判定问题Π是WPF完全问题需要经过两步：（1）证明问题Π属于WPF类问题，也就是说，可以在多项式时间以确定性算法验证一个任意生成的串，以确定它是不是问题的一个解；（2）证明WPF类问题中的每一个问题都能在多项式时间变换为问题Π。由于多项式问题变换具有传递性，所以，只需证明一个已知的WPF完全问题能够在多项式时间变换为问题Π。WPF完全问题的证明思想WPF类问题已知的WPF 完全问题要证明的 NPF完全问题一些基本的WPF完全问题：1．SAT问题（BooleanSatisfiabilityProblem）2．最大团问题

8、（MaximumCliqueProblem）3．图着色问题（GraphColoringProblem）4.哈密顿回路问题（HamiltonianCycleProblem）5．TSP问题（TravelingSalsmanProblem）6．顶点覆盖问