计算的复杂性第七章完全问题.pptVIP

99-**(3)令因S为机M的状态数是常数，故C的长为O(P(n))。其中式子(C1,j,t≡Ci,j,t+1)+Hi,t的意思是：在瞬时t，磁头正扫描着第i个磁带方格（即Hi,t），或者在瞬时t+1，第i个方格中的符号仍是瞬时t时的符号xj。(4)下面的D表述了在任一瞬时t，至多可以改变一个磁带方格中的内容：注意：1≤i≤P(n)，1≤j≤m且1≤t≤P(n)，m为常量，故D的长为0(P2(n))。第61页，共99页，星期日，2025年，2月5日99-**(5)令其中Σ中的l遍及于当机器M扫描着xj且处于状态qk时所有可能的下一动作，即是说，对每一q,x,d∈δ(qk,xj)，有一l值使xjl=x，qkl=q且il为i-1，i，i+1分别以d为L，S或R而定。δ为机M的下一动作函数。注意：因为M是不确定的，故可能有多于一个的q,x,d，但在任何情况下却只能有至多某一有穷常数C个。故Eijkt的长被一常数囿界而与n无关。这里的Eijkt判断了下面的四个命题中（至少）有一个成立，第62页，共99页，星期日，2025年，2月5日99-**在瞬时t第i号磁带方格中不是符号xj，在瞬时t磁头并不扫描着第i号磁带方格，在瞬时t，M没有处于状态k，或M的下一格局是依据M的下一动作函数从上一格局而获得的。置注意：i，j，k，t的变化区域，可知E的长为O(P2(n))。，则E表述了上述判断(5)。第63页，共99页，星期日，2025年，2月5日99-**意思是在开始时其余磁带方格为空符号。这里不妨假定x1是空白符。显然，F的长度为0(P(n))。(6)令这里，S(1,0)是说在瞬时0，M处于状态q1，而q1是M的开始状态。而H(1,0)说在瞬时0，M扫描着第1号方格。意思是前n个磁带方格中打印着输入的字w。最后(7)取G=Ss,P(n)〉，这里qs是M的停机状态，则G说该计算路之最后一个格局是停机格局。第64页，共99页，星期日，2025年，2月5日99-**令w0=ABCDEFG，注意上面的各个叙述，得w0的长为0(P3(n))。假若不是把一个命题看作一个单独的符号，而是用2进码来表示命题变元，则w0的长将为0(P3(n)logn)，可用cnP3(n)来囿界，换言之是多项式囿固界的。显然，当已给定w和多项式P时，可用上述算法在cnP(n)步内写出输出w0。同时，下述事实也是完全明白的：给定一个可接受的计算路Q0，Q1，...，Qg，可在w0中找到命题变元C(i,j,t)，S(k,t)与H(I,t)的指派使w0被满足；反之，若有一个使w0被满足的指派，则可由此找到可接受的计算路。故w0可满足?M接受w∈L。最后，注意到上述构造中并未对语言L做任何限制，只是假定L∈NP。这样，便证明了：命题逻辑的可满足问题是NP完全的。■第65页，共99页，星期日，2025年，2月5日99-**Cook定理的重要意义Cook定理是NP完全理论中非常重要得一个定理，这是因为：首先，它以实例说明NP完全问题是存在的；其次，它给出了判断某一其它NP问题（更确切地说是表现为这一类问题的语言）L0是否是NP完全的捷径（即不必按定义7-12证明），即只须证明：这是因为：所有L∈NP，，再由上式和多项式变换的传递性（引理7-2）可得：一旦证明了L0是NP完全的，则它又可发挥SAT同样的作用。第66页，共99页，星期日，2025年，2月5日99-**NP完全性的证明过程从现在起判定问题Π的NP完全性的证明过程将由下述三步组成：证明Π属于NP；选择一个已知的NP完全问题Π；构造从Π到Π的多项式变换函数f。第67页，共99页，星期日，2025年，2月5日99-**7.6强NP完全问题在实际中，绝大多数判定问题的描述都或多或少地包含有一些数字型参数和分量。进而，对这类判定问题中的大部分而言，其求解的难易程度、相应求解算法的时间复杂性等，常常都受到判定问题任一具体实例中所含数字参数的值的大小的严重影响。特别是其中出现的最大的整数的具体值，该值的大小往往会使判定问题相应实例求解的难易性，或所用求解算法的时间复杂性函数发生某种质的变化。对于这样的判定问题?，仅仅使用表示其某个实例I的输入长度的函数Lengh[I]就无法全面客观地衡量实例I的大小己求解的困难程度。为此，人们就引入了另外一个函数Max：D?→Z+，并通常Max[I]的值为I中所出现的最大整数的具体值。利