1521非确定性图灵机 在图灵机计算模型中,移动函数δ是单值的,即对于QxTK 中的每一个值,当它属于δ的定义域时,Qx(T×{L,R,S})k中只 有唯一的值与之对应,称这种图灵机为确定性图灵机,简记为 DTM(Deterministic Turing machine)o 非确定性图灵机(NDTM):一个k带的非确定性图灵机 M是一个7元组:(Q,T,I,δ,b,q,qH)。与确定性图灵机不 同的是非确定性图灵机允许移动函数δ具有不确定性,即对于 QxT中的每一个值(qX1X2x…×),当它属于δ的定义域时 Q×(Tx{L,R,S)中有唯一的一个子集6(X1X2…×)与之对应。 可以在δ(qX1×2…,X)中随意选定一个值作为它的函数值
11 15.2.1 非确定性图灵机 非确定性图灵机（ NDTM ）：一个k带的非确定性图灵机 M是一个7元组：(Q，T，I，δ，b，q0，qf )。与确定性图灵机不 同的是非确定性图灵机允许移动函数δ具有不确定性，即对于 QT k中的每一个值(q;x1 ,x2 ,…,xk )，当它属于δ的定义域时， Q(T{L，R，S})k中有唯一的一个子集δ(q;x1 ,x2 ,…,xk )与之对应。 可以在δ(q;x1 ,x2 ,…,xk )中随意选定一个值作为它的函数值。 在图灵机计算模型中，移动函数δ是单值的，即对于QT k 中的每一个值，当它属于δ的定义域时，Q(T{L，R，S})k中只 有唯一的值与之对应，称这种图灵机为确定性图灵机，简记为 DTM(Deterministic Turing Machine)
1522P类与NP类语言 P类和NP类语言的定义 P={LL是一个能在多项式时间内被一台DTM所接受 的语言} NP={L是一个能在多项式时间内被一台NDTM所 接受的语言} 由于一台确定性图灵机可看作是非确定性图 灵机的特例,所以可在多项式时间内被确定性图灵 机接受的语言也可在多项式时间内被非确定性图灵 机接受。故PcNP
12 15.2.2 P类与NP类语言 P类和NP类语言的定义： P={L|L是一个能在多项式时间内被一台DTM所接受 的语言} NP={L|L是一个能在多项式时间内被一台NDTM所 接受的语言} 由于一台确定性图灵机可看作是非确定性图 灵机的特例，所以可在多项式时间内被确定性图灵 机接受的语言也可在多项式时间内被非确定性图灵 机接受。故P NP
1522P类与NP类语言 NP类语言举例无向图的团问题。 该问题的输入是一个有n个顶点的无向图G=(V,E)和 一个整数k。要求判定图G是否包含一个k页点的完全子 图(团),即判定是否存在VV,Vl=k,且对于所有的 u,V∈V,有(u,V∈E。 若用邻接矩阵表示图G,用二进制串表示整数k,则 团问题的一个实例可以用长度为n2+的工进位串表示。 因此,团问题可表示为语言: CLIQUE={w#W,V∈0,1y,以w为邻接矩阵的 图G有一个k顶点的团,其中∨是k的二进制表示。}
13 15.2.2 P类与NP类语言 NP类语言举例——无向图的团问题。 该问题的输入是一个有n个顶点的无向图G=(V，E)和 一个整数k。要求判定图G是否包含一个k顶点的完全子 图(团)，即判定是否存在V’V，|V’|=k，且对于所有的 u，v∈V’ ，有(u，v)∈E。 若用邻接矩阵表示图G，用二进制串表示整数k，则 团问题的一个实例可以用长度为 的二进位串表示。 因此，团问题可表示为语言： CLIQUE={w#v|w，v∈{0，1}*，以w为邻接矩阵的 图G有一个k顶点的团，其中v是k的二进制表示。} log 1 2 n + k +
1522P类与NP类语言 接受该语言 CLIQUE的非确定性算法:用非确定性选择指令选 出包含k个顶点的候选顶点子集∨,然后确定性地检查该子集是否 是团问题的一个解。算法分为3个阶段 算法的第一阶段将输入串w执分解,并计算出n=Ⅶw以及用 V表示的整数k。若输入不具有形式W#或W不是一个平方数就拒 绝该输入。显而易见,第一阶段可(在刑间内完成。 在算法的第二阶段中,非确定性地选择V的一个k元子集VsV。 算法的第三阶段是确定性地检查V的团性质。若V是一个团则 接受输入,否则拒绝输入。这显然可以在(间内完成。因此 整个算法的时间复杂性为 o(n 非确定性算法在多项式时间内接受语言 CLIQUE,故 CLIQUE∈NP
14 15.2.2 P类与NP类语言 接受该语言CLIQUE的非确定性算法：用非确定性选择指令选 出包含k个顶点的候选顶点子集V，然后确定性地检查该子集是否 是团问题的一个解。算法分为3个阶段： 算法的第一阶段将输入串w#v分解，并计算出n= ，以及用 v表示的整数k。若输入不具有形式w#v或|w|不是一个平方数就拒 绝该输入。显而易见，第一阶段可 在时间内完成。 | w| ( ) 2 O n 在算法的第二阶段中，非确定性地选择V的一个k元子集V’V。 算法的第三阶段是确定性地检查V’的团性质。若V’是一个团则 接受输入，否则拒绝输入。这显然可以在 时间内完成。因此， 整个算法的时间复杂性为 。 ( ) 4 O n ( ) 4 O n 非确定性算法在多项式时间内接受语言CLIQUE，故 CLIQUE∈NP