《算法分析与设计技术》第二章 P类、NP类及NPC类

第二章P类、NP类及NPC类2.1问题与算法2.2确定型图灵机与P类2.3非确定型计算与NP类2.4多项式变换与NPC类2.1问题与算法☆定义2-1:算法是一步一步求解问题的通用程序。

☆问题的两个要素

:实例（输入）询问（输出）☆问题的形式分为两类：优化问题判定问题2.2确定型图灵(Turning)机与P类☆确定型单带图灵机构造如下图：

图2-1确定型单带图灵机☆定义2-2:如果把问题л的任意实例I输入给DTM，都能经过DTM程序的有限步计算到达停机状态qf，则称问题л是图灵可计算的，否则称为图灵不可计算的。☆定义2-3:问题<∑,∟,φ>是用某个DTM程序M可解的，即图灵可计算的，是指下列条件成立：对于∀I∈L，只要把I写在带上（其两侧填写空白符号，读写头扫描着I的最左端符号所在的方格）

,由起始状态q0开始执行DTM程序M，总可经过有限步计算停机，且在带上保留着该问题的解答φ(I)。☆定义2-4:设L(n)={I}，则称TM(n)=max{TM(I)}

为求解问题<∑,∟,φ>的DTM程序M的时间复杂性。类似地SM(n)=max{SM(I)}

为求解问题<∑,∟,φ>的DTM程序M的空间复杂性。☆定义2-5:如果存在多项式P，使得对所有n∈z+均有TM(n)≤P(n)，那么称DTM程序M为多项式时间的。如果一个问题存在解它的多项式时间DTM程序M，那么称该问题属于P类。2.3非确定型计算与NP类☆定义2-6:当判定问题的任一实例I∈L输入到NTM时，都能经过NTM程序的某可能动作序列的有限步计算到达停机状态qf，则称判定问题π为NTM可解（非确定型图灵机可计算），否则称为NTM不可解（非确定型图灵机不可计算）。☆定义2-7:当判定问题π用NTM程序M可解时，对于Φ(I)=1（在停机状态qY终止）的实例I而言，M的非确定型时间复杂性NTM(n)和非确定型空间复杂性NSM(n)可定义为在得到‘YES’回答的动作序列中至少所需要的计算步数和带方格数。若设L(n)={I∣I∈L,Ф(I)=1,∣I∣=n}

则称 NTM(n)=max{NTM(1)}

I∈L(n)

NSM(n)=max{NSM(1)}

I∈L(n)

为NTM程序M的非确定型时间复杂行和空间复杂性。☆定义2-8:如果存在多项式P，使得对所有n∈z+，均有NTM(n)≤P(n),那么称NTM程序M为多项式时间的。如果一个问题有求解它的多项式时间NTM程序，则称该问题属于NP类。☆定理2-1:如果问题π属于类，那么存在一个多项式P和求解问题π的程序M，使TM(n)=O(2p(n))。2.4多项式变换与NPC类☆定义2-9:在判定问题π1=(∑1,L1,Φ1)和π2=(∑2,L2,Φ2)之间，若存在如下变换，f:∑1*→∑2*,f(L1)⊆L2且∀I∈L1恒有Φ1(I)=Φ2(f(I))。并且可用某个DTM程序在∣I∣=n的多项式时间内计算出f(I)。则称判定问题π1可多项式变换成π2

，f为从π1到π2的变换，记为π1∝π2

。☆引理2-1:若π1∝π2

，则若判定问题π2属于P类必有判定问题π1属于P类。☆引理2-2:若π1∝π2

，π2∝π3

，则π1∝π3

。☆定义2-10:对于判定问题π1和π2

，如果既有π1∝π2

，又有π2∝π1

，那么称π1和π2是多项式等价的。☆定义2-11:若判定问题π∈NP，而且对每个判定问题π′∈NP，都有π′∈π，则称判定问题π属于NPC类，或称判定问题π为NP完全的。☆定理2-2：设问题π∈NPC类，则下述两条件等价：

1)P≠NP2)π不属于P。☆定理2-3：如果判定问题π1和π2都属于NP类，π1属于NPC类，并且π1∝π2

，那么π2也属于NPC类。☆定义2-12：如果SAT问题归约成问题L，则称问题L是NP难解的。如果L是NP难解的且L∈NP，则称问题L是NP完全的。

证明新问题