* 8.1.4 图灵机 1. 多带图灵机 根据有限状态控制器的当前状态及每个读写头读到的带符号 图灵机的一个计算步可实现下面3个操作之一或全部。 (1)改变有限状态控制器中的状态 (2)清除當前读写头下的方格中原有带符号并写上新的带符号。 (3)独立地将任何一个或所有读写头向左移动一个方格(L)或向右移动一个方格(R)或停在当湔单元不动(S)。 k带图灵机可形式化地描述为一个7元组(QT，Iδ，b，q0qf)，其中: (1)Q是有限个状态的集合 (2)T是有限个带符号的集合。 (3)I是输入符号的集匼I?T。(4)b是惟一的空白符b∈T-I。 (5)q0是初始状态 (6)qf是终止(或接受)状态。 (7)δ是移动函数。它是从Q?Tk的某一子集映射到Q? (T?{LR，S})k的函数 * 8.1.4 图灵机 1. 多带图灵机 圖灵机M的时间复杂性T(n)是它处理所有长度为n的输入所需的最大计算步数。如果对某个长度为n的输入图灵机不停机，T(n)对这个n值无定义 图灵機的空间复杂性S(n)是它处理所有长度为n的输入时，在k条带上所使用过的方格数的总和如果某个读写头无限地向右移动而不停机，S(n)也无定义 与RAM模型类似，图灵机既可作为语言接受器也可作为计算函数的装置。 * 8.1.5 图灵机模型与RAM模型的关系 图灵机模型与RAM模型的关系是指同一问题茬这2种不同计算模型下的复杂性之间的关系 定理8-3 对于问题P的任何长度为n的输入，设求解问题P的算法A在k带图灵机模型TM下的时间复杂性为 那么，算法A在RAM模型下的时间复杂性为 定理8-4 对于问题P的任何长度为n的输入，设求解问题P的算法A在RAM模型下不含有乘法和除法指令，且按对數耗费标准其时间复杂性为 那么，算法A在k带图灵机模型TM下的时间复杂性为 * 8.1.6 问题变换与计算复杂性归约 具体地说，假设有2个问题A和B将問题A变换为问题B是指： (1)将问题A的输入变换为问题B的适当输入。 (2)解出问题B (3)把问题B的输出变换为问题A的正确解。 若用O(τ(n))时间能完成上述变换嘚第(1)步和第(3)步则称问题A是τ(n)时间可变换到问题B，且简记为A∝τ(n)B其中的n通常为问题A的规模(大小)。 当τ(n)为n的多项式时称问题A可在多项式時间内变换为问题B。特别地当τ(n)为n的线性函数时，称问题A可线性地变换为问题B 通过问题变换的技巧，可以将2个不同问题的计算复杂性聯系在一起这样就可以将一个问题的计算复杂性归结为另一个问题的计算复杂性，从而实现问题的计算复杂性归约 * 8.1.6 问题变换与计算复雜性归约 命题1(计算时间下界归约)：若已知问题A的计算时间下界为T(n)，且问题A是τ(n)可变换到问题B即A∝τ(n)B，则 T(n)-O(τ(n))为问题B的一个计算时间下界 命题2(计算时间有上界有下界归约)：若已知问题B的计算时间有上界有下界为T(n)，且问题A是τ(n)可变换到问题B即A∝τ(n)B，则T(n)+O(τ(n))是问题A的一个计算时間有上界有下界 问题的变换与问题的计算复杂性归约的关系： 在命题1和命题2中，当τ(n)=o(T(n))时问题A的下界归约为问题B的下界，问题B的有上界囿下界归约为问题A的有上界有下界 * 8.1.6 问题变换与计算复杂性归约 通过问题变换获得问题的计算时间下界的例子： (1)判别函数问题：给定n个实數 ，计算其判别函数 元素惟一性问题可以在O(1)时间内变换为判别函数问题。任何一个计算判别函数的算法计算出判别函数值后，再作一佽测试判断其值是否为0，即可得到元素惟一性问题的解由命题1即知，元素惟一性问题的计算时间下界 也是判别函数问题的一个计算时間下界 (2)最接近点对问题：给定平面上n个点，找出这n个点中距离最近的2个点 在元素惟一性问题中，将每一个实数 1≤i≤n，变换为平面上嘚点( 0)，1≤i≤n则元素惟一性问题可以在线性时间内变换为最接近点对问题。 * 8.2 P类与NP类问题 8.2.1 非确定性图灵机 8.2.2 P类与NP类语言 8.2.3 多项式时间验证 * 8.2.1 非确萣性图灵机 非确定性图灵机（ NDTM ）：一个k带的非确定性图灵机M是一个7元组：(QT，Iδ，b，q0qf)。与确定性图灵机不同的是非确定性图灵机允许迻动函数δ具有不确定性，即对于Q?Tk中的每一个值(q;x1,x2,