【学术论文】时间复杂性和空间复杂性研究

第9卷第5期 智能系统学报 Vol.9 No.5 2014年10月 CAAI Transactions on Intelligent Systems 0ct.2014 D0:10.3969/j.issn.1673-4785.201311055 时间复杂性和空间复杂性研究 高强，徐心和 (东北大学信息科学与工程学院，辽宁沈阳110004) 摘要：计算复杂性是衡量问题求解的难易程度的。研究问题的计算复杂性，可以明确该问题是否存在有效的求解 算法。介绍并分析了计算理论的一些基本概念，论述了时间复杂性（包括P、NP、NP-hard、NP-complete和EXPTIME) 和空间复杂性（包括PSPACE,NPSPACE、PSPACE-hard和PSAPCE-complete)中的各个主要分类。最后分析了各个复 杂性类之间的关系。 关键词：计算复杂性：图灵机；确定型多项式时间复杂性：非确定型多项式时间复杂性：非确定型多项式时间复杂性 的完全问题：确定型多项式空间复杂性：确定型多项式空间复杂性的完全问题：可归约性 中图分类号：TP301.5文献标志码：A文章编号：1673-4785(2014)05-0529-07 中文引用格式：高强，徐心和.时间复杂性和空间复杂性研究[J].智能系统学报，2014,9(5)：529-535. 英文引用格式：GAO Qiang,XU Xinhe.Research on time complexity and space complexity[J].CAAI Transactions on Intelligent Systems,2014,9(5):529-535. Research on time complexity and space complexity GAO Qiang,XU Xinhe (College of Information Science and Engineering,Northeastern University,Shenyang 110004,China) Abstract:Computational complexity is used to measure the level of difficulty of a problem being solved.The re- search on computational complexity of the problem can make it explicit.This paper introduces and analyzes some fundamental concepts of the computation theory and discusses some main classes of time complexity (including P, NP,NP-hard,NP-complete and EXPTIME)and space complexity including PSPACE,NPSPACE,PSPACE- hard and PSAPCE-complete)by examples.Finally the relations among complexity classes are analyzed. Keywords:computational complexity;Turing machine;P;NP;NP-complete;PSAPCE;PSAPCE-complete;re- ducibility 理论与实践是密切相关的，计算理论为实际工 地了解计算机的能力及局限性。研究问题的复杂性 作者提供了在计算机工程中使用的理性工具[)。 可以了解该问题求解的难易程度，如果它被证明是 计算复杂性是计算理论的重要分支，它告诉人们问 难解的，就不必将大量精力花费在寻找有效的求解 题求解需要多少资源（时间或空间）。它所涉及到 算法上[)，从而在实际工作中做出理性的抉择。本 的一些典型的难解问题包括旅行商问题[)、SAT问 文介绍了与计算复杂性相关的基本概念，同时综述 题（可满足性问题，它涉及芯片测试、计算机设计、 了目前的研究状况，通过例子分析了各个计算复杂 软件工程等应用领域[])、电路复杂性问题)、博弈 性类的特点及其证明的方法。并对各个计算复杂性 问题]等。通过对计算复杂性的研究，可以更深入 类之间的关系作了详细的分析。 收稿日期：2013-11-22. 1计算复杂性 基金项目：国家自然科学基金资助项目(61370153). 通信作者：高强.E-mail:ommy_06@163.com 计算复杂性是计算理论的一个分支，它用于衡

第 ９ 卷第 ５ 期 智 能 系 统 学 报 Ｖｏｌ．９ №．５ ２０１４ 年 １０ 月 ＣＡＡＩ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ Ｏｃｔ． ２０１４ ＤＯＩ：１０．３９６９ ／ ｊ．ｉｓｓｎ．１６７３⁃４７８５．２０１３１１０５５ 时间复杂性和空间复杂性研究 高强， 徐心和 （东北大学 信息科学与工程学院，辽宁 沈阳 １１０００４） 摘 要：计算复杂性是衡量问题求解的难易程度的。 研究问题的计算复杂性，可以明确该问题是否存在有效的求解 算法。 介绍并分析了计算理论的一些基本概念，论述了时间复杂性（包括 Ｐ、ＮＰ、ＮＰ⁃ｈａｒｄ、ＮＰ⁃ｃｏｍｐｌｅｔｅ 和 ＥＸＰＴＩＭＥ） 和空间复杂性（包括 ＰＳＰＡＣＥ、ＮＰＳＰＡＣＥ、ＰＳＰＡＣＥ⁃ｈａｒｄ 和 ＰＳＡＰＣＥ⁃ｃｏｍｐｌｅｔｅ）中的各个主要分类。 最后分析了各个复 杂性类之间的关系。 关键词：计算复杂性；图灵机； 确定型多项式时间复杂性；非确定型多项式时间复杂性；非确定型多项式时间复杂性 的完全问题；确定型多项式空间复杂性；确定型多项式空间复杂性的完全问题；可归约性 中图分类号： ＴＰ３０１．５ 文献标志码：Ａ 文章编号：１６７３⁃４７８５（２０１４）０５⁃０５２９⁃０７ 中文引用格式：高强， 徐心和． 时间复杂性和空间复杂性研究［Ｊ］． 智能系统学报， ２０１４， ９（５）： ５２９⁃５３５． 英文引用格式：ＧＡＯ Ｑｉａｎｇ， ＸＵ Ｘｉｎｈｅ． Ｒｅｓｅａｒｃｈ ｏｎ ｔｉｍｅ ｃｏｍｐｌｅｘｉｔｙ ａｎｄ ｓｐａｃｅ ｃｏｍｐｌｅｘｉｔｙ［ Ｊ］． ＣＡＡＩ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ， ２０１４， ９（５）： ５２９⁃５３５． Ｒｅｓｅａｒｃｈ ｏｎ ｔｉｍｅ ｃｏｍｐｌｅｘｉｔｙ ａｎｄ ｓｐａｃｅ ｃｏｍｐｌｅｘｉｔｙ ＧＡＯ Ｑｉａｎｇ， ＸＵ Ｘｉｎｈｅ （Ｃｏｌｌｅｇｅ ｏｆ Ｉｎｆｏｒｍａｔｉｏｎ Ｓｃｉｅｎｃｅ ａｎｄ Ｅｎｇｉｎｅｅｒｉｎｇ， Ｎｏｒｔｈｅａｓｔｅｒｎ Ｕｎｉｖｅｒｓｉｔｙ， Ｓｈｅｎｙａｎｇ １１０００４，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｃｏｍｐｕｔａｔｉｏｎａｌ ｃｏｍｐｌｅｘｉｔｙ ｉｓ ｕｓｅｄ ｔｏ ｍｅａｓｕｒｅ ｔｈｅ ｌｅｖｅｌ ｏｆ ｄｉｆｆｉｃｕｌｔｙ ｏｆ ａ ｐｒｏｂｌｅｍ ｂｅｉｎｇ ｓｏｌｖｅｄ． Ｔｈｅ ｒｅ⁃ ｓｅａｒｃｈ ｏｎ ｃｏｍｐｕｔａｔｉｏｎａｌ ｃｏｍｐｌｅｘｉｔｙ ｏｆ ｔｈｅ ｐｒｏｂｌｅｍ ｃａｎ ｍａｋｅ ｉｔ ｅｘｐｌｉｃｉｔ． Ｔｈｉｓ ｐａｐｅｒ ｉｎｔｒｏｄｕｃｅｓ ａｎｄ ａｎａｌｙｚｅｓ ｓｏｍｅ ｆｕｎｄａｍｅｎｔａｌ ｃｏｎｃｅｐｔｓ ｏｆ ｔｈｅ ｃｏｍｐｕｔａｔｉｏｎ ｔｈｅｏｒｙ ａｎｄ ｄｉｓｃｕｓｓｅｓ ｓｏｍｅ ｍａｉｎ ｃｌａｓｓｅｓ ｏｆ ｔｉｍｅ ｃｏｍｐｌｅｘｉｔｙ （ｉｎｃｌｕｄｉｎｇ Ｐ， ＮＰ， ＮＰ⁃ｈａｒｄ， ＮＰ⁃ｃｏｍｐｌｅｔｅ ａｎｄ ＥＸＰＴＩＭＥ） ａｎｄ ｓｐａｃｅ ｃｏｍｐｌｅｘｉｔｙ （ ｉｎｃｌｕｄｉｎｇ ＰＳＰＡＣＥ， ＮＰＳＰＡＣＥ， ＰＳＰＡＣＥ⁃ ｈａｒｄ ａｎｄ ＰＳＡＰＣＥ⁃ｃｏｍｐｌｅｔｅ） ｂｙ ｅｘａｍｐｌｅｓ． Ｆｉｎａｌｌｙ ｔｈｅ ｒｅｌａｔｉｏｎｓ ａｍｏｎｇ ｃｏｍｐｌｅｘｉｔｙ ｃｌａｓｓｅｓ ａｒｅ ａｎａｌｙｚｅｄ． Ｋｅｙｗｏｒｄｓ：ｃｏｍｐｕｔａｔｉｏｎａｌ ｃｏｍｐｌｅｘｉｔｙ； Ｔｕｒｉｎｇ ｍａｃｈｉｎｅ； Ｐ； ＮＰ； ＮＰ⁃ｃｏｍｐｌｅｔｅ； ＰＳＡＰＣＥ； ＰＳＡＰＣＥ⁃ｃｏｍｐｌｅｔｅ； ｒｅ⁃ ｄｕｃｉｂｉｌｉｔｙ 收稿日期：２０１３⁃１１⁃２２． 基金项目：国家自然科学基金资助项目（６１３７０１５３）． 通信作者：高强．Ｅ⁃ｍａｉｌ：ｔｏｍｍｙ＿０６＠ １６３．ｃｏｍ． 理论与实践是密切相关的，计算理论为实际工 作者提供了在计算机工程中使用的理性工具［１］ 。 计算复杂性是计算理论的重要分支，它告诉人们问 题求解需要多少资源（时间或空间）。 它所涉及到 的一些典型的难解问题包括旅行商问题［２］ 、ＳＡＴ 问 题（可满足性问题，它涉及芯片测试、计算机设计、 软件工程等应用领域［２］ ）、电路复杂性问题［３］ 、博弈 问题［１］等。 通过对计算复杂性的研究，可以更深入 地了解计算机的能力及局限性。 研究问题的复杂性 可以了解该问题求解的难易程度，如果它被证明是 难解的，就不必将大量精力花费在寻找有效的求解 算法上［１］ ，从而在实际工作中做出理性的抉择。 本 文介绍了与计算复杂性相关的基本概念，同时综述 了目前的研究状况，通过例子分析了各个计算复杂 性类的特点及其证明的方法。 并对各个计算复杂性 类之间的关系作了详细的分析。 １ 计算复杂性 计算复杂性是计算理论的一个分支，它用于衡

·530· 智能系统学报 第9卷 量问题被求解所需资源（比如时间或空间）的多 0,并且0的个数是奇数，则拒绝； 少山，在介绍时间复杂性和空间复杂性之前，先来 4)读写头返回至带子的最左端： 了解计算理论中的一些基本概念。 5)转到第1)步。 1.1可判定问题 第1)步每重复一次，就会消去带子上一半的0。 可判定问题是指该问题在算法上是可解的，即 如果执行一次第1)步后，带子上的0的个数是大于 该问题在计算模型（如有穷自动机或图灵机）上执 1的奇数，说明带子上原有的0的个数不可能是2 行，能够进入接受或拒绝状态而终止计算（即停机 的方幂，因此拒绝山。显然该算法M2判定该语言。 状态)。不可判定问题是指该问题在算法上是不 对于存储资源有限的有穷自动机是无法描述该算法 可解的，即该问题在计算模型上执行不能进入停机 的，而对于下推自动机，虽然具有无限存储的栈，但 状态，即不停机」 由于栈的“先进后出”的特点，无法实现隔一个字符 1.2确定型图灵机及非确定型图灵机 消去一个0，由此可见图灵机具有更强的描述问题 1.2.1确定型图灵机 的能力。 图灵机(deterministic Turing machine,DTM) 1.2.2非确定型图灵机 (见图1)是一种通用的计算模型)，该模型由图灵 确定型图灵机在计算过程中，下一步动作只有 (Alan Turing)在1936年提出)，能模拟实际计算机 一种可能：而非确定型图灵机[)(nondeterministic 的所有计算行为。它用一个无限长的带子作为它的 Turing machine,NTM)是指在计算过程中，机器可以 无限存储，有一个读写头，能在带子上读、写符号和 在多种可能性动作中选择一种继续进行，其计算是 左右移动。初始时，带子上只有输入串，其他地方都 一棵树，不同分支对应机器不同的可能性[)。如果 是空的，如果需要保存信息，它可能将这个信息写在 计算的某个分支导致接受状态，则机器接受该输入。 带子上，为了读已经写下的信息，它可将读写头往回 非确定型图灵机并不对应任何实际的计算设 移动到这个信息所在的位置。机器持续地计算，直 备，它是一种假想的机器)。但它是一个有用的数 到产生输出为止。机器预置了接受和拒绝2种状 学定义，有些问题更适于采用非确定型图灵机来描 态，如果进入这2种状态，就产生输出接受或拒绝。 述，如计算机博弈问题，某走棋方在走棋时有多种走 如果不能进入任何接受或拒绝状态，就继续执行下 法可选择，这与非确定型图灵机的计算过程相同。 去，永不停止。 每个非确定型图灵机都等价于一个确定型图灵 机)。也就是说这2种图灵机在能力上是等价的。 a BB B 文献[7]中给出如下定理：如果一个确定型图灵机 控制器 去模拟一个t(n)时间的非确定型图灵机，则所需时 间为2() 图1图灵机示意 1.3映射可归约性 Fig.1 The diagram of Turing machine 概念问题A是映射可归约到问题B的，如果 由于它具有无限的存储带，带上可读也可写，读 写头可在带上左右移动等特点，所以相对于另外2 存在可计算函数f,使得对每个W,0∈A台f(w)∈ 种计算模型一有穷自动机山（它的存储资源是有 B,记做A≤B。称f为A到B的归约山。 限的)和下推自动机山（其栈内信息“先进后出”）， 作用它旨在将一个问题转化为另一个问题， 它具有更强的描述求解某问题的算法的能力。例 且使得可以用第2个问题的解来解第1个问题。如 如：确定型图灵机可以判定语言A(即，所有由0组 果问题A可归约到问题B,就可用B的解来解决问 成、长度为2的方幂的字符串)，A={01n≥0}。 题A)。例如：在一个城市认路，可以借助于城市地 该语言（语言是对问题的形式化描述）)的算法描 图，这样就将城市认路问题归约到城市地图问题。 述DTMM,如下： 2 时间复杂性 对于输入字符串w: 1)从左往右扫描整个带子，隔一个字符消去一 时间复杂性是指求解一个问题所需多少时间。 个0： 对于固定规模的问题，其所需时间是一个常量：对于 2)如果在第1)步之后，带子上只剩下唯一的一 任意规模的问题，一般采用渐近记法[山，衡量其求 个0，则接受： 解的复杂程度。如：函数f(n)=n3+n2+1,利用渐 3)如果在第1)步之后，带子上包含不止一个 近记法，则该函数的时间复杂性为O(n3)(其中0

量问题被求解所需资源（ 比如时间或空间） 的多 少［１］ ，在介绍时间复杂性和空间复杂性之前，先来 了解计算理论中的一些基本概念。 １．１ 可判定问题 可判定问题是指该问题在算法上是可解的，即 该问题在计算模型（如有穷自动机或图灵机） 上执 行，能够进入接受或拒绝状态而终止计算（即停机 状态［４］ ）。 不可判定问题是指该问题在算法上是不 可解的，即该问题在计算模型上执行不能进入停机 状态，即不停机［４］ 。 １．２ 确定型图灵机及非确定型图灵机 １．２．１ 确定型图灵机 图灵 机 （ ｄｅｔｅｒｍｉｎｉｓｔｉｃ Ｔｕｒｉｎｇ ｍａｃｈｉｎｅ， ＤＴＭ） （见图 １）是一种通用的计算模型［５］ ，该模型由图灵 （Ａｌａｎ Ｔｕｒｉｎｇ）在 １９３６ 年提出［１］ ，能模拟实际计算机 的所有计算行为。 它用一个无限长的带子作为它的 无限存储，有一个读写头，能在带子上读、写符号和 左右移动。 初始时，带子上只有输入串，其他地方都 是空的，如果需要保存信息，它可能将这个信息写在 带子上，为了读已经写下的信息，它可将读写头往回 移动到这个信息所在的位置。 机器持续地计算，直 到产生输出为止。 机器预置了接受和拒绝 ２ 种状 态，如果进入这 ２ 种状态，就产生输出接受或拒绝。 如果不能进入任何接受或拒绝状态，就继续执行下 去，永不停止。 图 １ 图灵机示意 Ｆｉｇ．１ Ｔｈｅ ｄｉａｇｒａｍ ｏｆ Ｔｕｒｉｎｇ ｍａｃｈｉｎｅ 由于它具有无限的存储带，带上可读也可写，读 写头可在带上左右移动等特点，所以相对于另外 ２ 种计算模型———有穷自动机［１］ （它的存储资源是有 限的）和下推自动机［１］ （其栈内信息“先进后出”）， 它具有更强的描述求解某问题的算法的能力。 例 如：确定型图灵机可以判定语言 Ａ（即，所有由 ０ 组 成、长度为 ２ 的方幂的字符串）， Ａ ＝ ｛０ ２ ｎ ｜ ｎ ≥ ０｝ 。 该语言（语言是对问题的形式化描述［５］ ）的算法描 述［１］ＤＴＭ Ｍ ２如下： 对于输入字符串 ｗ： １）从左往右扫描整个带子，隔一个字符消去一 个 ０； ２）如果在第 １）步之后，带子上只剩下唯一的一 个 ０，则接受； ３） 如果在第 １） 步之后，带子上包含不止一个 ０，并且 ０ 的个数是奇数，则拒绝； ４）读写头返回至带子的最左端； ５）转到第 １）步。 第 １）步每重复一次，就会消去带子上一半的 ０。 如果执行一次第 １）步后，带子上的 ０ 的个数是大于 １ 的奇数，说明带子上原有的 ０ 的个数不可能是 ２ 的方幂，因此拒绝［１］ 。 显然该算法 Ｍ２ 判定该语言。 对于存储资源有限的有穷自动机是无法描述该算法 的，而对于下推自动机，虽然具有无限存储的栈，但 由于栈的“先进后出”的特点，无法实现隔一个字符 消去一个 ０，由此可见图灵机具有更强的描述问题 的能力。 １．２．２ 非确定型图灵机 确定型图灵机在计算过程中，下一步动作只有 一种可能； 而非确定型图灵机［５］ （ ｎｏｎｄｅｔｅｒｍｉｎｉｓｔｉｃ Ｔｕｒｉｎｇ ｍａｃｈｉｎｅ，ＮＴＭ）是指在计算过程中，机器可以 在多种可能性动作中选择一种继续进行，其计算是 一棵树，不同分支对应机器不同的可能性［５］ 。 如果 计算的某个分支导致接受状态，则机器接受该输入。 非确定型图灵机并不对应任何实际的计算设 备，它是一种假想的机器［７］ 。 但它是一个有用的数 学定义，有些问题更适于采用非确定型图灵机来描 述，如计算机博弈问题，某走棋方在走棋时有多种走 法可选择，这与非确定型图灵机的计算过程相同。 每个非确定型图灵机都等价于一个确定型图灵 机［１］ 。 也就是说这 ２ 种图灵机在能力上是等价的。 文献［７］中给出如下定理：如果一个确定型图灵机 去模拟一个 ｔ（ｎ）时间的非确定型图灵机，则所需时 间为 ２ Ｏ（ｔ（ｎ）） 。 １．３ 映射可归约性 概念 问题 Ａ 是映射可归约到问题 Ｂ 的，如果 存在可计算函数 ｆ ，使得对每个 ｗ， ｗ ∈ Ａ⇔ｆ（ｗ） ∈ Ｂ ，记做 Ａ ≤ｍ Ｂ 。 称 ｆ 为 Ａ 到 Ｂ 的归约［１］ 。 作用 它旨在将一个问题转化为另一个问题， 且使得可以用第 ２ 个问题的解来解第 １ 个问题。 如 果问题 Ａ 可归约到问题 Ｂ，就可用 Ｂ 的解来解决问 题 Ａ ［３］ 。 例如：在一个城市认路，可以借助于城市地 图，这样就将城市认路问题归约到城市地图问题。 ２ 时间复杂性 时间复杂性是指求解一个问题所需多少时间。 对于固定规模的问题，其所需时间是一个常量；对于 任意规模的问题，一般采用渐近记法［１］ ，衡量其求 解的复杂程度。 如：函数 ｆ（ｎ） ＝ ｎ ３ ＋ ｎ ２ ＋ １，利用渐 近记法，则该函数的时间复杂性为 Ｏ（ｎ ３ ） （其中 Ｏ ·５３０· 智 能 系 统 学 报 第 ９ 卷

第5期 高强，等：时间复杂性和空间复杂性研究 ·531. 表示一个常数)，因为最高次项的影响占主导地位。 NP类问题是否存在有效的多项式时间算法[)。但 另外，也可以通过证明，给一些问题的时间复杂性分 是去验证某个问题是否成立是可以在多项式时间完 类来说明该问题求解的难易程度。 成的】，比如：合数问题（当一个自然数是2个大于 2.1确定型多项式时间复杂性 1的整数的乘积，称该自然数为合数)，虽然还没有 确定型多项式时间复杂性(deterministic polyno- 找到一个有效的多项式时间算法，但可以比较容易 mial time,P)是指可以在确定型图灵机上以多项式 地去验证一个数是否是合数，这只需找到该数的一 时间解决的问题的集合6)。一般认为多项式时间 个因子)，比如24，它可以是4和6的乘积，因此它 算法已经足够快了，而指数时间的算法很少采 是合数。所以NP是具有多项式时间验证机（验证 用)。属于P复杂性类的问题，被认为是容易求解 算法)的问题的集合[山。 的)。属于P类的例子：2个数是否是互素的问题， NP类问题的举例判定一个无向图是否包含 即RELPRIME={(a,b〉Ia与b互素}[)：如果1 指定大小的团的问题属于NP[,令CLIQUE= 是同时整除2个数的最大整数，则称这2个数是互 {〈G,〉IG是包含k团的无向图}。 素的。如9和10就是互素的。一种快速地判断2 团的概念如果C是无向图的顶点集V的子 个数是否互素的方法是采用欧几里德算法(Euclide- 集，而且任意2个C中的顶点都有边连接，则称顶 an algorithm)【9)来计算2个自然数a和b的最大公 点集C为该无向图的团)。文献[1]给出一种判定 因子，记为gcd(x,y)【o,它是能够整除2个自然数 团的非确定型多项式时间算法，如下： 的最大整数，如：gcd(12,15)=3。显然若gcd N=“对输入〈G,〉，其中G是一个无向图： (x,y)=1,说明x和y是互素的。欧几里德算法用 1)非确定性地选择G中k个结点的子集； 伪代码描述如下： 2)检查G是否包含链接C中结点的所有边： function ged(a,6) 3)若是，则接受：否则，拒绝。” while b≠O 算法分析该算法是运行在非确定型图灵机 t←b(“←一”表示赋值)》 上，当然，现实中并没有这种设备，这是一种假想，假 b←-a mod b(“mod”表示求余运算) 设存在这种机器，该算法在非确定型图灵机上以多 a←-t 项式时间运行，而确定型图灵机才是现实中计算机 return a 的雏形，所以该算法在计算机上将以指数时间运行， 该算法输出的值就是a和b的最大公因子。 也就是说该算法是不可取的，说明团问题是难解的。 算法R以gcd(a,b)为子程序求解REL 2.3NP的完全问题(NP-complete) PRIMED。 一个语言B属于NP-complete,如果它满足2个 R=“对输入(a,b〉，a和b是自然数： 条件： 1)运行子程序gcd(a,b)。 1)B属于NP; 2)若结果为1，就接受：否则，就拒绝。” 2)每个属于NP的问题在多项式时间内可以归 算法R的复杂性分析：显然，算法R的复杂性 约到B。 由欧几里德算法的复杂性决定。欧儿里德算法的复 NP-complete问题被认为是NP类中最难的[2)] 杂性问题已经被彻底研究过了，其复杂性为h2(h为 Cook[12找到并证明了第一个属于NP-complete的问 2个自然数中最小的那个数的位数)山，因此算法 题a】,即SAT2(satisfiability,可满足性问题)， R的复杂性是h2,属于P类，即多项式时间算法。 可以根据映射可归约性，证明某个问题属于NP 2.2非确定型多项式时间复杂性 complete。如果某个问题被证明属于NP-complete, 非确定型多项式时间复杂性(nondeterministic 则说明该问题不存在有效的多项式时间算法，因此 polynomial time,NP)是指可以在非确定型图灵机上 就可以不用将精力花费在寻找有效算法上了。 以多项式时间解决的问题的集合[6。而前面在图 对于NP-complete的定义，如果B仅仅满足条件2， 灵机的阐述中提到过，一个确定型图灵机去模拟一 这说明该问题本身并不属于NP,可以说它是NP- 个t(n)时间的非确定型图灵机，所需时间为 hard山。因而该问题可能更加难解。 2(),所以属于P类的问题与属于NP类的问题 NP-complete例子顶点覆盖问题is)。 在求解的时间上存在指数级的差异。可见NP类的 无向图G的顶点覆盖是一个顶点集合V,使得 问题被怀疑是难解的[]。到目前为止，还不清楚 G中的每一条边都接触V中的至少一个顶点6

表示一个常数），因为最高次项的影响占主导地位。 另外，也可以通过证明，给一些问题的时间复杂性分 类来说明该问题求解的难易程度。 ２．１ 确定型多项式时间复杂性 确定型多项式时间复杂性（ｄｅｔｅｒｍｉｎｉｓｔｉｃ ｐｏｌｙｎｏ⁃ ｍｉａｌ ｔｉｍｅ，Ｐ）是指可以在确定型图灵机上以多项式 时间解决的问题的集合［６］ 。 一般认为多项式时间 算法已 经 足 够 快 了， 而 指 数 时 间 的 算 法 很 少 采 用［１］ 。 属于 Ｐ 复杂性类的问题，被认为是容易求解 的［８］ 。 属于 Ｐ 类的例子：２ 个数是否是互素的问题， 即 ＲＥＬＰＲＩＭＥ ＝ ｛〈ａ， ｂ〉 ｜ ａ 与 ｂ 互素｝ ［１］ ；如果 １ 是同时整除 ２ 个数的最大整数，则称这 ２ 个数是互 素的。 如 ９ 和 １０ 就是互素的。 一种快速地判断 ２ 个数是否互素的方法是采用欧几里德算法（Ｅｕｃｌｉｄｅ⁃ ａｎ ａｌｇｏｒｉｔｈｍ） ［９］来计算 ２ 个自然数 ａ 和 ｂ 的最大公 因子，记为 ｇｃｄ（ｘ，ｙ） ［１０］ ，它是能够整除 ２ 个自然数 的最 大 整 数， 如： ｇｃｄ（１２，１５） ＝ ３。 显 然 若 ｇｃｄ （ｘ，ｙ） ＝１，说明 ｘ 和 ｙ 是互素的。 欧几里德算法用 伪代码描述［９］如下： ｆｕｎｃｔｉｏｎ ｇｃｄ（ａ，ｂ） ｗｈｉｌｅ ｂ ≠ ０ ｔ ← ｂ（“←”表示赋值） ｂ ← ａ ｍｏｄ ｂ（“ｍｏｄ”表示求余运算） ａ ← ｔ ｒｅｔｕｒｎ ａ 该算法输出的值就是 ａ 和 ｂ 的最大公因子。 算法 Ｒ 以 ｇｃｄ（ａ，ｂ） 为 子 程 序 求 解 ＲＥＬ⁃ ＰＲＩＭＥ ［１］ 。 Ｒ ＝ “对输入〈ａ， ｂ〉，ａ 和 ｂ 是自然数： １）运行子程序 ｇｃｄ（ａ，ｂ） 。 ２）若结果为 １，就接受；否则，就拒绝。” 算法 Ｒ 的复杂性分析：显然，算法 Ｒ 的复杂性 由欧几里德算法的复杂性决定。 欧几里德算法的复 杂性问题已经被彻底研究过了，其复杂性为 ｈ ２ （ｈ 为 ２ 个自然数中最小的那个数的位数） ［１１］ ，因此算法 Ｒ 的复杂性是 ｈ ２ ，属于 Ｐ 类，即多项式时间算法。 ２．２ 非确定型多项式时间复杂性 非确定型多项式时间复杂性（ ｎｏｎｄｅｔｅｒｍｉｎｉｓｔｉｃ ｐｏｌｙｎｏｍｉａｌ ｔｉｍｅ，ＮＰ）是指可以在非确定型图灵机上 以多项式时间解决的问题的集合［６］ 。 而前面在图 灵机的阐述中提到过，一个确定型图灵机去模拟一 个 ｔ （ ｎ ） 时 间 的 非 确 定 型 图 灵 机， 所 需 时 间 为 ２ Ｏ（ｔ（ｎ）） ，所以属于 Ｐ 类的问题与属于 ＮＰ 类的问题 在求解的时间上存在指数级的差异。 可见 ＮＰ 类的 问题被怀疑是难解的［８］ 。 到目前为止，还不清楚 ＮＰ 类问题是否存在有效的多项式时间算法［８］ 。 但 是去验证某个问题是否成立是可以在多项式时间完 成的［１］ ，比如：合数问题（当一个自然数是 ２ 个大于 １ 的整数的乘积，称该自然数为合数），虽然还没有 找到一个有效的多项式时间算法，但可以比较容易 地去验证一个数是否是合数，这只需找到该数的一 个因子［１］ ，比如 ２４，它可以是 ４ 和 ６ 的乘积，因此它 是合数。 所以 ＮＰ 是具有多项式时间验证机（验证 算法）的问题的集合［１］ 。 ＮＰ 类问题的举例 判定一个无向图是否包含 指定大小的团的问题属于 ＮＰ ［１２］ ，令 ＣＬＩＱＵＥ ＝ ｛〈Ｇ， ｋ〉 ｜ Ｇ 是包含 ｋ 团的无向图｝。 团的概念 如果 Ｃ 是无向图的顶点集 Ｖ 的子 集，而且任意 ２ 个 Ｃ 中的顶点都有边连接，则称顶 点集 Ｃ 为该无向图的团［２］ 。 文献［１］给出一种判定 团的非确定型多项式时间算法，如下： Ｎ＝ “对输入〈Ｇ ， ｋ〉 ，其中 Ｇ 是一个无向图： １）非确定性地选择 Ｇ 中 ｋ 个结点的子集； ２）检查 Ｇ 是否包含链接 Ｃ 中结点的所有边； ３）若是，则接受；否则，拒绝。” 算法分析 该算法是运行在非确定型图灵机 上，当然，现实中并没有这种设备，这是一种假想，假 设存在这种机器，该算法在非确定型图灵机上以多 项式时间运行，而确定型图灵机才是现实中计算机 的雏形，所以该算法在计算机上将以指数时间运行， 也就是说该算法是不可取的，说明团问题是难解的。 ２．３ ＮＰ 的完全问题（ＮＰ⁃ｃｏｍｐｌｅｔｅ） 一个语言 Ｂ 属于 ＮＰ⁃ｃｏｍｐｌｅｔｅ，如果它满足 ２ 个 条件： １）Ｂ 属于 ＮＰ； ２）每个属于 ＮＰ 的问题在多项式时间内可以归 约到 Ｂ ［１］ 。 ＮＰ⁃ｃｏｍｐｌｅｔｅ 问题被认为是 ＮＰ 类中最难的［２］ ， Ｃｏｏｋ ［１２］找到并证明了第一个属于 ＮＰ⁃ｃｏｍｐｌｅｔｅ 的问 题［１３］ ，即 ＳＡＴ ［１２］ （ｓａｔｉｓｆｉａｂｉｌｉｔｙ， 可满足性问题［１４］ ）， 可以根据映射可归约性，证明某个问题属于 ＮＰ⁃ ｃｏｍｐｌｅｔｅ。 如果某个问题被证明属于 ＮＰ⁃ｃｏｍｐｌｅｔｅ， 则说明该问题不存在有效的多项式时间算法，因此 就可以不用将精力花费在寻找有效算法上了［１］ 。 对于 ＮＰ⁃ｃｏｍｐｌｅｔｅ 的定义，如果 Ｂ 仅仅满足条件 ２， 这说明该问题本身并不属于 ＮＰ，可以说它是 ＮＰ⁃ ｈａｒｄ ［１］ 。 因而该问题可能更加难解。 ＮＰ⁃ｃｏｍｐｌｅｔｅ 例子 顶点覆盖问题［１５］ 。 无向图 Ｇ 的顶点覆盖是一个顶点集合 Ｖ，使得 Ｇ 中的每一条边都接触 Ｖ 中的至少一个顶点［１６］ 。 第 ５ 期 高强，等：时间复杂性和空间复杂性研究 ·５３１·

.532. 智能系统学报 第9卷 顶点覆盖问题旨在确定图中是否存在指定规模的顶 可以在顶点覆盖问题上求解，根据NP-complete定 点覆盖： 义可知，顶，点覆盖问题属于NP-complete。 VERTEX-COVER={(G,k〉IG是具有k个 2.4指数时间复杂性(exponential time,EXPTIME) 结点的顶点覆盖的无向图}山，顶点覆盖问题属于 该复杂性类是一些确定型问题的集合，这些问 NP-complete类问题2。 题可以使用确定型图灵机在O(2()的时间内解 对于证明某个问题A属于NP-complete,需要依 决，这里的p(n)代表的是n的某个多项式。属于该 据NP-complete的定义，具体步骤如下： 复杂性的问题，它的难度不小于P、NP、NP-complete 1)证明A属于NP; 以及空间复杂性类(PSPACE和PSPACE-com- 2)需要找到一个已被证明是NP-complete的问 plete)rl。 题B; EXPTIME例子G,[)]游戏，该游戏中的每个 3)证明B可归约到A: 局面(position)是一个四元组(r,W-LOSE(X,Y), 4)证明该归约可在多项式时间内完成。 B-L0SE(X,Y),a'),其中r∈{W,B},它表示当前 这里步骤3)是难点，需要一些别出心裁的巧妙 走棋方，W-LOSE=C:VC2VCsV.VCp和 思维去构造一个合理的归约函数，文献[1]中，使用 B-L0SE=C1VC2VC3V…VC,是属于 已经被证明属于NP-complete的问题3SAT(3SAT, 12DNF的布尔公式，其中每个C:(1≤i≤P)和 是一个合取范式，该公式中每一个子句都有3个文 C2(1≤j≤q)是最多12个文字之间的与运算，每个 字，它是Karp]的21个NP-complete问题的其中之 文字是集合X(Y)中的一个变量，如：z或：（变量z 一)，设该3SAT公式为(x Vx V y)A(元VyVy) 的非运算)；a'是对公式XUY的一个赋值，如：X= ∧(xVyV),并且构造了一个归约，如图2。 {x1,x2,x3},Y={y1y2,y3},则XUY={xl,x2,x3, 变量构件一 y1,y2,y3},对XUY赋值，就是对该集合中的各个 元素赋值为0或1。 比赛双方交替进行，W方或B方通过改变集合 X和Y中的一个变量的值进行走棋。更精确地，W 方能够从局面(W,W-L0SE(X,Y),B-LOSE(X, Y),a')下棋到局面(B,W-LOSE(X,Y),B-LOSE 子句构件一 (X,Y),a),当且仅当a'与a’不同，并且在'的 图2归约的完整结构图 赋值下，W-L0SE(X,Y)的布尔值为false。如果在 Fig.2 The complete structure of reducibility W(B)走了若干步后，公式W-LOSE(B-LOSE)为 图中包括变量构件和子句构件，变量构件关系 rue,那么W(B)失败。 对变量的赋值：子句构件对应公式中的3个子句。 在文献[17]中，给出了四元组中的公式F(即 图中共有2m+3l(m表示公式中变量的数量，l表 W-LOSE(X,Y)或B-LOSE(X,Y))的所有可能的表 示公式中子句的数量)个顶点，令指定的顶点覆盖 示形式共有：card(V(F))≤e×FI /log(IFI), 规模k=m+l,根据此3SAT公式，k的值为8，因此 其中，e为常量，IFI表示公式F被编码后的长度，V 要从图中找到满足该3SAT公式的规模为8的顶点 (F)表示公式F所有可能的表示形式所构成的集 覆盖。 合，card(V(F))表示集合中的元素总数。而对于表 规则山首先为2个变量选取满足公式的赋 示G,游戏局面的四元组，对于player I(playerⅡ)， 值，即x为假、y为真，选择变量构件中相应的结点 通过对集合X(Y)中的一个变量的赋值来完成下 作为顶点覆盖中的结点，然后在各个子句构件中选 棋，而该变量的值有2个，即0或1。所以，某个走 择值不为真的2个结点作为顶点覆盖中的结点，其 棋方在下棋时，可走的局面有2个，即对于一个F的 中第3个子句的3个变量的值都为真，则将不影响 表示形式，由于四元组有2种可能，所以，从第一步 顶点覆盖的结点无去除，选择该子句中的另外2个 开始一直到分出胜负，共有e×|F1/log(1F1)个2 结点，如图中有阴影的结点，这些结点的集合构成该 相乘，即2eIA)。又用r来识别走棋方，即第 图的一个顶点覆盖。因此说明该图中的顶点覆盖， 一步谁先走有2种可能，并且该四元组中有2个公 可以满足该3SAT公式（即该公式的值为真），进而 式F(即W-LOSE(X,Y)和B-LOSE(X,Y)),因此 说明3SAT可归约到顶点覆盖，也就是说3SAT问题 对一个输入w,其中n表示w的长度，则G:从开始

顶点覆盖问题旨在确定图中是否存在指定规模的顶 点覆盖： ＶＥＲＴＥＸ⁃ＣＯＶＥＲ ＝ ｛〈Ｇ ， ｋ〉 ｜ Ｇ 是具有 ｋ 个 结点的顶点覆盖的无向图｝ ［１］ ，顶点覆盖问题属于 ＮＰ⁃ｃｏｍｐｌｅｔｅ 类问题［１２］ 。 对于证明某个问题 Ａ 属于 ＮＰ⁃ｃｏｍｐｌｅｔｅ，需要依 据 ＮＰ⁃ｃｏｍｐｌｅｔｅ 的定义，具体步骤如下： １）证明 Ａ 属于 ＮＰ； ２）需要找到一个已被证明是 ＮＰ⁃ｃｏｍｐｌｅｔｅ 的问 题 Ｂ； ３）证明 Ｂ 可归约到 Ａ； ４）证明该归约可在多项式时间内完成。 这里步骤 ３）是难点，需要一些别出心裁的巧妙 思维去构造一个合理的归约函数，文献［１］中，使用 已经被证明属于 ＮＰ⁃ｃｏｍｐｌｅｔｅ 的问题 ３ＳＡＴ（３ＳＡＴ， 是一个合取范式，该公式中每一个子句都有 ３ 个文 字，它是 Ｋａｒｐ ［１２］的 ２１ 个 ＮＰ⁃ｃｏｍｐｌｅｔｅ 问题的其中之 一），设该 ３ＳＡＴ 公式为 （ｘ ∨ ｘ ∨ ｙ） ∧ （ｘ － ∨ ｙ － ∨ ｙ － ） ∧ （ｘ － ∨ ｙ ∨ ｙ － ） ，并且构造了一个归约，如图 ２。 图 ２ 归约的完整结构图 Ｆｉｇ．２ Ｔｈｅ ｃｏｍｐｌｅｔｅ ｓｔｒｕｃｔｕｒｅ ｏｆ ｒｅｄｕｃｉｂｉｌｉｔｙ 图中包括变量构件和子句构件，变量构件关系 对变量的赋值；子句构件对应公式中的 ３ 个子句。 图中共有 ２ｍ ＋ ３ｌ （ｍ 表示公式中变量的数量，ｌ 表 示公式中子句的数量） 个顶点，令指定的顶点覆盖 规模 ｋ ＝ ｍ ＋ ｌ ，根据此 ３ＳＡＴ 公式，ｋ 的值为 ８，因此 要从图中找到满足该 ３ＳＡＴ 公式的规模为 ８ 的顶点 覆盖。 规则［１］ 首先为 ２ 个变量选取满足公式的赋 值，即 ｘ 为假、ｙ 为真，选择变量构件中相应的结点 作为顶点覆盖中的结点，然后在各个子句构件中选 择值不为真的 ２ 个结点作为顶点覆盖中的结点，其 中第 ３ 个子句的 ３ 个变量的值都为真，则将不影响 顶点覆盖的结点 ｘ － 去除，选择该子句中的另外 ２ 个 结点，如图中有阴影的结点，这些结点的集合构成该 图的一个顶点覆盖。 因此说明该图中的顶点覆盖， 可以满足该 ３ＳＡＴ 公式（即该公式的值为真），进而 说明 ３ＳＡＴ 可归约到顶点覆盖，也就是说 ３ＳＡＴ 问题 可以在顶点覆盖问题上求解，根据 ＮＰ⁃ｃｏｍｐｌｅｔｅ 定 义可知，顶点覆盖问题属于 ＮＰ⁃ｃｏｍｐｌｅｔｅ。 ２．４ 指数时间复杂性（ｅｘｐｏｎｅｎｔｉａｌ ｔｉｍｅ， ＥＸＰＴＩＭＥ） 该复杂性类是一些确定型问题的集合，这些问 题可以使用确定型图灵机在 Ｏ（２ ｐ（ｎ） ） 的时间内解 决，这里的 ｐ（ｎ）代表的是 ｎ 的某个多项式。 属于该 复杂性的问题，它的难度不小于 Ｐ、ＮＰ、ＮＰ⁃ｃｏｍｐｌｅｔｅ 以及 空 间 复 杂 性 类 （ ＰＳＰＡＣＥ 和 ＰＳＰＡＣＥ⁃ｃｏｍ⁃ ｐｌｅｔｅ） ［３］ 。 ＥＸＰＴＩＭＥ 例子 Ｇ３ ［１７］ 游戏，该游戏中的每个 局面（ｐｏｓｉｔｉｏｎ）是一个四元组（ τ ， Ｗ－ＬＯＳＥ（Ｘ，Ｙ）， Ｂ－ＬＯＳＥ（Ｘ，Ｙ），α′），其中 τ ∈ ｛Ｗ，Ｂ｝ ，它表示当前 走棋方， Ｗ － ＬＯＳＥ ＝ Ｃ１１ ∨ Ｃ１２ ∨ Ｃ１３ ∨ … ∨ Ｃ１ｐ 和 Ｂ⁃ＬＯＳＥ ＝ Ｃ２１ ∨ Ｃ２２ ∨ Ｃ２３ ∨ … ∨ Ｃ２ｑ 是属于 １２ＤＮＦ ［１８］的布尔公式，其中每个 Ｃ１ ｉ（１≤ｉ≤ｐ） 和 Ｃ２ ｊ（１≤ｊ≤ｑ）是最多 １２ 个文字之间的与运算，每个 文字是集合 Ｘ（Ｙ）中的一个变量，如： ｚ 或 ｚ － （变量 ｚ 的非运算）；α′是对公式 Ｘ ∪ Ｙ 的一个赋值，如： Ｘ ＝ ｛ｘ１ ，ｘ２ ，ｘ３ ｝ ， Ｙ ＝ ｛ｙ１ ，ｙ２ ，ｙ３ ｝ ，则 Ｘ ∪Ｙ ＝ ｛ｘ１，ｘ２ ，ｘ３ ， ｙ１ ，ｙ２ ，ｙ３ ｝ ，对 Ｘ ∪ Ｙ 赋值，就是对该集合中的各个 元素赋值为 ０ 或 １。 比赛双方交替进行，Ｗ 方或 Ｂ 方通过改变集合 Ｘ 和 Ｙ 中的一个变量的值进行走棋。 更精确地，Ｗ 方能够从局面（ Ｗ， Ｗ － ＬＯＳＥ（Ｘ，Ｙ），Ｂ － ＬＯＳＥ （ Ｘ， Ｙ）， α′） 下棋到局面（Ｂ， Ｗ－ＬＯＳＥ（Ｘ，Ｙ）， Ｂ－ＬＯＳＥ （Ｘ，Ｙ）， α′），当且仅当 α′ 与 α′’不同，并且在 α′的 赋值下，Ｗ－ＬＯＳＥ（Ｘ，Ｙ） 的布尔值为 ｆａｌｓｅ。 如果在 Ｗ（Ｂ）走了若干步后，公式 Ｗ－ＬＯＳＥ（Ｂ －ＬＯＳＥ） 为 ｔｒｕｅ，那么 Ｗ（Ｂ）失败。 在文献［１７］ 中，给出了四元组中的公式 Ｆ（即 Ｗ－ＬＯＳＥ（Ｘ，Ｙ）或 Ｂ－ＬＯＳＥ（Ｘ，Ｙ））的所有可能的表 示形式共有： ｃａｒｄ（Ｖ（Ｆ）） ≤ ｅ ×｜ Ｆ ｜ ／ ｌｏｇ（｜ Ｆ ｜ ） ， 其中，ｅ 为常量， ｜ Ｆ ｜ 表示公式 Ｆ 被编码后的长度，Ｖ （Ｆ）表示公式 Ｆ 所有可能的表示形式所构成的集 合，ｃａｒｄ（Ｖ（Ｆ））表示集合中的元素总数。 而对于表 示 Ｇ３游戏局面的四元组，对于 ｐｌａｙｅｒ Ｉ（ ｐｌａｙｅｒ ＩＩ）， 通过对集合 Ｘ（ Ｙ） 中的一个变量的赋值来完成下 棋，而该变量的值有 ２ 个，即 ０ 或 １。 所以，某个走 棋方在下棋时，可走的局面有 ２ 个，即对于一个 Ｆ 的 表示形式，由于四元组有 ２ 种可能，所以，从第一步 开始一直到分出胜负，共有 ｅ ×｜ Ｆ ｜ ／ ｌｏｇ（｜ Ｆ ｜ ） 个 ２ 相乘，即 ２ ｅ×｜ Ｆ｜ ／ ｌｏｇ（｜ Ｆ｜ ） 。 又用 τ 来识别走棋方，即第 一步谁先走有 ２ 种可能，并且该四元组中有 ２ 个公 式 Ｆ（即 Ｗ－ＬＯＳＥ（Ｘ，Ｙ）和 Ｂ－ＬＯＳＥ（Ｘ，Ｙ）），因此， 对一个输入 ｗ，其中 ｎ 表示 ｗ 的长度，则 Ｇ ３从开始 ·５３２· 智 能 系 统 学 报 第 ９ 卷

第5期 高强，等：时间复杂性和空间复杂性研究 ·533· 走棋到分出胜负，共产生的局面的数量为2× 复使用，根据萨维奇定理0]，如果一台非确定型图 22esm,用渐近记法表示，为2(w1so),是指数级 灵机能够利用f(n)空间解决某个问题，那么一台确 的。即该游戏属于EXPTIME问题。 定型图灵机能够在至多f2(n)空间解决相同的问 3 空间复杂性 题。由该定理可得推论：NPSPACE=PSPACE)。 3.3 PSPACE的完全问题 空间复杂性是指求解一个问题所需多少空间。 一个语言B属于PSPACE的完全问题[) 属于某空间复杂性类的问题，它的求解难度要大于 (PSPACE-complete),如果它满足2个条件： 属于时间复杂性类的问题，因为运行快的算法不可 1)B属于PSPACE; 能消耗大量的空间，也就是说在每个计算步上最多 2)每个属于PSPACE的问题在多项式时间内 能访问一个新单元，所以，任何在时间t(n)内运行 归约到B。 的机器最多能消耗t(n)的空间山。与时间复杂性 PSPACE-complete属于PSPACE类中最困难的 一样，也是采用渐近记法来计算求解问题的空间复 问题，和NP-complete的定义类似，如果B仅仅满足 杂性。另外，也可以通过证明，给一些问题的空间复 条件2，说明B不属于PSPACE,可以说它是 杂性分类来说明该问题求解的困难程度。 PSPACE-hard,那么B可能更加难解。常见的属于 3.1确定型多项式空间复杂性 PSPACE-complete的问题有QBF[6(量词的布尔公 确定型多项式空间复杂性(deterministic polyno- 式)、formula game(公式博弈)、棋类游戏)(chess mial space,PSPACE)是指能够被确定型图灵机在多 game)等。 项式空间内解决的问题的集合[9)。属于PSPACE 举例广义地理学游戏1(generalized geogra- 问题举例：全量词化的布尔公式(true qualified bool-- phy game)是一种地理学游戏，选手们轮流给出世界 ean formula,TQBF)[o,形如：x3y(x∧y),该公 各地的城市名称。每一座选中的城市的首字母必须 式的含义是：对于任意的x,存在y,使得x八y为真。 与前一座城市的尾字母相同，城市的名称不允许重 全量词化的布尔公式是指公式中出现的所有变量， 复，游戏从某个指定的城市开始，直到某一方不能延 都有量词对其约束[6。TQBF问题就是判定一个全 续为止。对于证明某问题属于PSPACE-complete的 量词化的布尔公式是真或假的问题，它属于 过程与NP-complete的证明类似，首先要证明该问 PSPACE。其多项式空间算法)如下： 题属于PSPACE,文献[1]中给出了一个多项式空间 T=对输入的全量词化的布尔公式： 的算法，证明了该问题可在多项式空间求解。然后 1)若该公式不含量词，则它是一个只有常数的 选择了一个已被证明为PSPACE-complete类的问题 表达式。计算公式的值，若为真，则接受；否则，则拒 如formula game(实际上，它就是TQBF,只是假设有 绝。 2个选手交替为每个变量赋值)并独出心裁地构造 2)若公式等于3xp,在p上递归地调用T,首 了一个归约，如图3 先用0替换x,然后用1替换x。只要有一个结果是 True (b)False 接受，则接受：否则，拒绝。 3)若p等于Vxp,在p上递归调用T,首先用 0替换x,然后用1替换x。若2个结果都是接受，则 接受：否则，拒绝。 算法分析该算法模拟的是量词化布尔公式的 计算过程，每一次递归就是对公式中最左侧的一个 量词所约束的变量赋值（假设该公式为前束范 式1)。递归的深度就是该公式中中包含的变量的 个数，设为m,因此每层只需存储一个变量，所以该 算法的空间消耗是O(m)。因此该算法属于多项式 空间算法。 3.2 NPSPACE 它是指能够被非确定型图灵机在多项式空间内 图3归约的全部结构 解决的问题的集合。空间与时间不同，它可以被重 Fig.3 The complete structure of reducibility

走棋 到 分 出 胜 负， 共 产 生 的 局 面 的 数 量 为 ２ × ２ ２ｅｎ／ ｌｏｇ（ｎ） ，用渐近记法表示，为 ２ Ｏ（ｎ／ ｌｏｇ（ｎ）） ，是指数级 的。 即该游戏属于 ＥＸＰＴＩＭＥ 问题。 ３ 空间复杂性 空间复杂性是指求解一个问题所需多少空间。 属于某空间复杂性类的问题，它的求解难度要大于 属于时间复杂性类的问题，因为运行快的算法不可 能消耗大量的空间，也就是说在每个计算步上最多 能访问一个新单元，所以，任何在时间 ｔ（ ｎ）内运行 的机器最多能消耗 ｔ（ ｎ）的空间［１］ 。 与时间复杂性 一样，也是采用渐近记法来计算求解问题的空间复 杂性。 另外，也可以通过证明，给一些问题的空间复 杂性分类来说明该问题求解的困难程度。 ３．１ 确定型多项式空间复杂性 确定型多项式空间复杂性（ｄｅｔｅｒｍｉｎｉｓｔｉｃ ｐｏｌｙｎｏ⁃ ｍｉａｌ ｓｐａｃｅ，ＰＳＰＡＣＥ）是指能够被确定型图灵机在多 项式空间内解决的问题的集合［１９］ 。 属于 ＰＳＰＡＣＥ 问题举例：全量词化的布尔公式（ｔｒｕｅ ｑｕａｌｉｆｉｅｄ ｂｏｏｌ⁃ ｅａｎ ｆｏｒｍｕｌａ，ＴＱＢＦ） ［６］ ，形如： ∀ｘ∃ｙ（ｘ ∧ ｙ） ，该公 式的含义是：对于任意的 ｘ，存在 ｙ，使得 ｘ ∧ ｙ 为真。 全量词化的布尔公式是指公式中出现的所有变量， 都有量词对其约束［６］ 。 ＴＱＢＦ 问题就是判定一个全 量词 化 的 布 尔 公 式 是 真 或 假 的 问 题， 它 属 于 ＰＳＰＡＣＥ。 其多项式空间算法［１］如下： Ｔ ＝ 对输入的全量词化的布尔公式： １）若该公式不含量词，则它是一个只有常数的 表达式。 计算公式的值，若为真，则接受；否则，则拒 绝。 ２）若公式等于∃ ｘφ ，在 φ 上递归地调用 Ｔ，首 先用 ０ 替换 ｘ，然后用 １ 替换 ｘ。 只要有一个结果是 接受，则接受；否则，拒绝。 ３）若 φ 等于 ∀ｘφ ，在 φ 上递归调用 Ｔ，首先用 ０ 替换 ｘ，然后用 １ 替换 ｘ。 若 ２ 个结果都是接受，则 接受；否则，拒绝。 算法分析 该算法模拟的是量词化布尔公式的 计算过程，每一次递归就是对公式中最左侧的一个 量词所约束的变量赋值 （ 假设该公式为前束范 式［１８］ ）。 递归的深度就是该公式 φ 中包含的变量的 个数，设为 ｍ，因此每层只需存储一个变量，所以该 算法的空间消耗是 Ｏ（ｍ）。 因此该算法属于多项式 空间算法。 ３．２ ＮＰＳＰＡＣＥ 它是指能够被非确定型图灵机在多项式空间内 解决的问题的集合。 空间与时间不同，它可以被重 复使用，根据萨维奇定理［２０］ ，如果一台非确定型图 灵机能够利用 ｆ（ｎ）空间解决某个问题，那么一台确 定型图灵机能够在至多 ｆ ２ （ ｎ） 空间解决相同的问 题。 由该定理可得推论： ＮＰＳＰＡＣＥ ＝ ＰＳＰＡＣＥ ［１］ 。 ３．３ ＰＳＰＡＣＥ 的完全问题 一个 语 言 Ｂ 属 于 ＰＳＰＡＣＥ 的 完 全 问 题［１］ （ＰＳＰＡＣＥ⁃ｃｏｍｐｌｅｔｅ），如果它满足 ２ 个条件： １）Ｂ 属于 ＰＳＰＡＣＥ； ２）每个属于 ＰＳＰＡＣＥ 的问题在多项式时间内 归约到 Ｂ。 ＰＳＰＡＣＥ⁃ｃｏｍｐｌｅｔｅ 属于 ＰＳＰＡＣＥ 类中最困难的 问题，和 ＮＰ⁃ｃｏｍｐｌｅｔｅ 的定义类似，如果 Ｂ 仅仅满足 条件 ２， 说 明 Ｂ 不 属 于 ＰＳＰＡＣＥ， 可 以 说 它 是 ＰＳＰＡＣＥ⁃ｈａｒｄ，那么 Ｂ 可能更加难解。 常见的属于 ＰＳＰＡＣＥ⁃ｃｏｍｐｌｅｔｅ 的问题有 ＱＢＦ ［６］ （量词的布尔公 式）、ｆｏｒｍｕｌａ ｇａｍｅ ［１］ （公式博弈）、棋类游戏［１］ （ｃｈｅｓｓ ｇａｍｅ）等。 举例 广义地理学游戏［１］ （ ｇｅｎｅｒａｌｉｚｅｄ ｇｅｏｇｒａ⁃ ｐｈｙ ｇａｍｅ）是一种地理学游戏，选手们轮流给出世界 各地的城市名称。 每一座选中的城市的首字母必须 与前一座城市的尾字母相同，城市的名称不允许重 复，游戏从某个指定的城市开始，直到某一方不能延 续为止。 对于证明某问题属于 ＰＳＰＡＣＥ⁃ｃｏｍｐｌｅｔｅ 的 过程与 ＮＰ⁃ｃｏｍｐｌｅｔｅ 的证明类似，首先要证明该问 题属于 ＰＳＰＡＣＥ，文献［１］中给出了一个多项式空间 的算法，证明了该问题可在多项式空间求解。 然后 选择了一个已被证明为 ＰＳＰＡＣＥ⁃ｃｏｍｐｌｅｔｅ 类的问题 如 ｆｏｒｍｕｌａ ｇａｍｅ（实际上，它就是 ＴＱＢＦ，只是假设有 ２ 个选手交替为每个变量赋值）并独出心裁地构造 了一个归约，如图 ３ ［１］ 。 图 ３ 归约的全部结构 Ｆｉｇ．３ Ｔｈｅ ｃｏｍｐｌｅｔｅ ｓｔｒｕｃｔｕｒｅ ｏｆ ｒｅｄｕｃｉｂｉｌｉｔｙ 第 ５ 期 高强，等：时间复杂性和空间复杂性研究 ·５３３·

.534. 智能系统学报 第9卷 这是一个广义地理学的有向图，在该图上模拟 (P和NP)类的问题。 进行formula game,设布尔公式为 4.3空间复杂性与EXPTIME的关系 3xYx23x3x.3x(Vx2 Vx3)A (x2 Vx3 根据文献[1]中的引理：设M是有q个状态和 V…)A…∧()]，从图中顶端的b点开始，2个选 g个带符号的LBA(一种受限制的图灵机)。对于长 手1和Ⅱ分别给变量选择赋值（设x,x2,…,x处 度为n的带子，M恰有qng”个不同的格局。可推 的左侧结点表示1，右侧表示0)，最终某一方因无法 出，需要空间为f(n)的PSPACE问题，根据渐近记 选择结点（根据广义地理学游戏的规则，图中每个 法，最多有f(n)×2》个不同的格局，假设处理 结点只能选择一次)而输掉比赛，即比赛结束，该归 每个格局需要一个时间单元，在最差的情况下（遍 约确保：如果公式为rue,则选手I获胜；否则选手Ⅲ 历到第f代n)×2》个格局，图灵机输出接受或拒 获胜。这说明在广义地理学游戏上模拟进行Fo 绝，即处于停机状态)，求解该问题所用时间等于 mula Game,并最终能够求解。因此证明了Formula f代n)×2)。即该PSPACE问题必定在时间 Game可归约到广义地理学游戏。结合PSPACE- f(n)×2Ua)内运行，因此PSPACE≤ complete的定义，可知广义地理学问题属于 EXPTIME)。所以，各个计算复杂性类之间的关 PSPACE-complete。 系为P C NP C PSPACE=NPSPACE EXPTIME,如图4。 4各种复杂性类之间的关系 前文介绍了常见的时间复杂性类和空间复杂性 类，下面来讨论这些复杂性类中哪个相对简单，哪个 相对更加难解。 NP PSPACE EXPTIME 4.1P与NP的关系 P是在确定型图灵机上以多项式时间求解的问 题的集合：NP是在非确定型图灵机上以多项式时间 求解的问题的集合；NP问题若在确定型图灵机上求 图4各复杂性类之间的关系 解，就需要用确定型图灵机去模拟非确定型图灵机 Fig.4 The relations of some complexities 的运行过程，这种模拟所需要的时间是指数级的，因 此，普遍认为NP问题要难于P类问题，即P≤ 结束语 NP[)。但是否P=NP,有许多学者都在致力于这 计算复杂性是计算理论的一个分支，它是一个 方面的研究工作，如果P=NP,那么所有NP问题 理论性很强的计算机科学问题，极具挑战性。通过 都能够找到有效的多项式时间算法，也就是说许多 研究问题的计算复杂性，可以了解该问题求解的难 难解的问题都可以迎刃而解。但是还没有成功)， 易程度，如果是难解的（如NP-complete、PSPACE- 大多数学者还是接受P≠NP[2),COOK[]证明了 complete),即该问题不存在有效的多项式时间求解 第一个属于NP-complete的问题一可满足性问题 算法，则不必将大量的精力放在寻找该问题的有效 (satisfiability,SAT),同时根据映射可归约性，在某 算法上，从而提高了工作效率。论述了计算理论的 种意义上，是将所有NP问题归为了同一个问题[。 一些基本概念，并通过例子论述了各个计算复杂性 这为研究P和NP是否相等的学者们提供了一个方 类的证明方法和当前计算复杂性理论的研究现状。 便，即只要证明一个NP-complete问题存在有效的 最后详细分析了各个复杂性类之间的关系。在该领 多项式时间算法，那么所有的NP问题都存在多项 域中，还存在一些尚待解决的难题，比如：P是否等 式时间算法[] 于NP,许多学者都在致力于这方面的研究工作，如 4.2时间复杂性与空间复杂性的关系 果P=NP,那么所有NP问题都能够找到有效的多 前面已经提到过，运行快的算法不可能消耗大 项式时间算法，也就是说许多难解的问题都可以迎 量的空间，也就是说在每个计算步上最多能访问一 刃而解。但是这个等式还没有被成功证明：各个复 个新单元，所以，任何在时间t(n)内运行的机器最 杂性类之间的包含关系是否正确也有疑问，这些包 多能消耗t(n)的空间山。因此空间复杂性类 含关系是否存在着真包含，这些都是国内外学者们 (PSPACE和NPSPACE)的问题要难于时间复杂性 今后重点研究的课题

这是一个广义地理学的有向图，在该图上模拟 进 行 ｆｏｒｍｕｌａ ｇａｍｅ， 设 布 尔 公 式 为 ∃ｘ１∀ｘ２∃ｘ３∀ｘ４…∃ｘｋ［（ｘ１ ∨ ｘ２ ∨ ｘ３ ） ∧ （ｘ２ ∨ ｘ３ ∨…） ∧ … ∧ （）］ ，从图中顶端的 ｂ 点开始，２ 个选 手 Ｉ 和 ＩＩ 分别给变量选择赋值（设 ｘ１ ， ｘ２ ， …， ｘｋ处 的左侧结点表示 １，右侧表示 ０），最终某一方因无法 选择结点（根据广义地理学游戏的规则，图中每个 结点只能选择一次）而输掉比赛，即比赛结束，该归 约确保：如果公式为 ｔｒｕｅ，则选手 Ｉ 获胜；否则选手 ＩＩ 获胜。 这说明在广义地理学游戏上模拟进行 Ｆｏｒ⁃ ｍｕｌａ Ｇａｍｅ，并最终能够求解。 因此证明了 Ｆｏｒｍｕｌａ Ｇａｍｅ 可归约到广义地理学游戏。 结合 ＰＳＰＡＣＥ⁃ ｃｏｍｐｌｅｔｅ 的 定 义， 可 知 广 义 地 理 学 问 题 属 于 ＰＳＰＡＣＥ⁃ｃｏｍｐｌｅｔｅ。 ４ 各种复杂性类之间的关系 前文介绍了常见的时间复杂性类和空间复杂性 类，下面来讨论这些复杂性类中哪个相对简单，哪个 相对更加难解。 ４．１ Ｐ 与 ＮＰ 的关系 Ｐ 是在确定型图灵机上以多项式时间求解的问 题的集合；ＮＰ 是在非确定型图灵机上以多项式时间 求解的问题的集合；ＮＰ 问题若在确定型图灵机上求 解，就需要用确定型图灵机去模拟非确定型图灵机 的运行过程，这种模拟所需要的时间是指数级的，因 此，普遍认为 ＮＰ 问题要难于 Ｐ 类问题，即 Ｐ ⊆ ＮＰ ［３］ 。 但是否 Ｐ ＝ ＮＰ ，有许多学者都在致力于这 方面的研究工作，如果 Ｐ ＝ ＮＰ ，那么所有 ＮＰ 问题 都能够找到有效的多项式时间算法，也就是说许多 难解的问题都可以迎刃而解。 但是还没有成功［１］ ， 大多数学者还是接受 Ｐ ≠ ＮＰ ［２］ ，ＣＯＯＫ ［１３］ 证明了 第一个属于 ＮＰ⁃ｃｏｍｐｌｅｔｅ 的问题———可满足性问题 （ｓａｔｉｓｆｉａｂｉｌｉｔｙ， ＳＡＴ），同时根据映射可归约性，在某 种意义上，是将所有 ＮＰ 问题归为了同一个问题［２］ 。 这为研究 Ｐ 和 ＮＰ 是否相等的学者们提供了一个方 便，即只要证明一个 ＮＰ⁃ｃｏｍｐｌｅｔｅ 问题存在有效的 多项式时间算法，那么所有的 ＮＰ 问题都存在多项 式时间算法［２］ 。 ４．２ 时间复杂性与空间复杂性的关系 前面已经提到过，运行快的算法不可能消耗大 量的空间，也就是说在每个计算步上最多能访问一 个新单元，所以，任何在时间 ｔ（ ｎ）内运行的机器最 多能 消 耗 ｔ （ ｎ） 的 空 间［１］ 。 因 此 空 间 复 杂 性 类 （ＰＳＰＡＣＥ 和 ＮＰＳＰＡＣＥ）的问题要难于时间复杂性 （Ｐ 和 ＮＰ）类的问题。 ４．３ 空间复杂性与 ＥＸＰＴＩＭＥ 的关系 根据文献［１］中的引理：设 Ｍ 是有 ｑ 个状态和 ｇ 个带符号的 ＬＢＡ（一种受限制的图灵机）。 对于长 度为 ｎ 的带子， Ｍ 恰有 ｑｎｇ ｎ 个不同的格局。 可推 出，需要空间为 ｆ（ ｎ）的 ＰＳＰＡＣＥ 问题，根据渐近记 法，最多有 ｆ（ｎ） × ２ Ｏ（ｆ（ｎ）） 个不同的格局，假设处理 每个格局需要一个时间单元，在最差的情况下（遍 历到第 ｆ（ｎ） × ２ Ｏ（ｆ（ｎ）） 个格局，图灵机输出接受或拒 绝，即处于停机状态），求解该问题所用时间等于 ｆ（ｎ） × ２ Ｏ（ｆ（ｎ）） 。 即该 ＰＳＰＡＣＥ 问题必定在时间 ｆ（ｎ） × ２ Ｏ（ｆ（ｎ）） 内 运 行， 因 此 ＰＳＰＡＣＥ ⊆ ＥＸＰＴＩＭＥ ［３］ 。 所以，各个计算复杂性类之间的关 系 为 Ｐ ⊆ ＮＰ ⊆ ＰＳＰＡＣＥ ＝ ＮＰＳＰＡＣＥ ⊆ ＥＸＰＴＩＭＥ ［１］ ， 如图 ４。 图 ４ 各复杂性类之间的关系 Ｆｉｇ．４ Ｔｈｅ ｒｅｌａｔｉｏｎｓ ｏｆ ｓｏｍｅ ｃｏｍｐｌｅｘｉｔｉｅｓ ５ 结束语 计算复杂性是计算理论的一个分支，它是一个 理论性很强的计算机科学问题，极具挑战性。 通过 研究问题的计算复杂性，可以了解该问题求解的难 易程度，如果是难解的（ 如 ＮＰ⁃ｃｏｍｐｌｅｔｅ、 ＰＳＰＡＣＥ⁃ ｃｏｍｐｌｅｔｅ），即该问题不存在有效的多项式时间求解 算法，则不必将大量的精力放在寻找该问题的有效 算法上，从而提高了工作效率。 论述了计算理论的 一些基本概念，并通过例子论述了各个计算复杂性 类的证明方法和当前计算复杂性理论的研究现状。 最后详细分析了各个复杂性类之间的关系。 在该领 域中，还存在一些尚待解决的难题，比如：Ｐ 是否等 于 ＮＰ，许多学者都在致力于这方面的研究工作，如 果 Ｐ ＝ ＮＰ ，那么所有 ＮＰ 问题都能够找到有效的多 项式时间算法，也就是说许多难解的问题都可以迎 刃而解。 但是这个等式还没有被成功证明；各个复 杂性类之间的包含关系是否正确也有疑问，这些包 含关系是否存在着真包含，这些都是国内外学者们 今后重点研究的课题。 ·５３４· 智 能 系 统 学 报 第 ９ 卷

第5期 高强，等：时间复杂性和空间复杂性研究 .535. [14]ZHANG Lintao.Searching for truth:techniques for satisfi- 参考文献： ability of boolean formulas[D].Princeton:Princeton Uni- [1]SIPSER M.Introduction to the theory of computation M] versity,2003:10-14. 2nd ed.Beijing:China Machine Press,2006:265-323. [15]CORMEN T H,LEISERSON C H,RIVEST R L,et al. [2]DASGUPTA S,PAPADIMITRIOU C H,VAZI-RANI U V. Introduction to algorithms[M].2nd ed.Cambridge,Mas- Algorithm[M].New York:McGraw-Hill Science/Engineer- sachusetts:MIT Press,2009:1108-1110. ing/Math,2006:257-264. [16]VERTEX COVER DB/OL ][2013-10-19].http://zh. [3]PAPADIMITRIOU C.Computational complexity[M].Read- wikipedia.org/wiki/VERTEX COVER. ing,Massachusetts:Addison-Wesley,1994:491-493. [17]STOCKMEYER L J,CHANDRA A K.Provably difficult [4]朱一清.可计算性与计算复杂性[M].北京：国防工业出 combinatorial games J].SIAM J Compuf,1979 8(2): 版社，2006：44-45. 151-174. [5]堵丁柱.计算复杂性导论[M].北京：高等教育出版社， [18]罗森离散数学及其应用[M].北京：机械工业出版社， 2000:21-22. 2011:21-30. [6]ARORA S,BARAK B.Computational complexity[M].New [19]PSPACE DB/OL].[2013-10-20 ]http://zh.wikipedia. York:Cambridge University Press,2007:24-85. org/wiki/PSPACE. [7]陈志平，徐宗本.计算机数学一计算复杂性理论与 [20]SAVITCH W J.Relationships between nondeterministic NPC、NP难问题的求解[M].北京：科学出版社，2001： and deterministic tape complexities[J].Journal of Com- 81-83. puter and System Sciences,1970 4(2):177-192. [8]NP DB/OL].2013-10-17].http://zh.wikipedia.or-g/ 作者简介： wiki/NP. 高强，男，1980年生，讲师，博士研 [9]COPRIME[DB/OL].2013-10-17].http://zh.wikiped-ia. 究生，主要研究方向为机器博弈、计算 org/wiki/COPRIME. 复杂性理论。 [10]GRAHAM R L,KNUTH D E,PATASHNIK O.Concrete mathematics[M].Massachusetts:Addison-Wesley,1989: 107-110. 徐心和，男，1940年生，教授，博士 [11]HONSBERGER R.Mathematical gems II[M].Washington, 生导师，中国人工智能学会常务理事， DC:The Mathematical Association of America,1976:54- 主要研究方向为控制理论与应用、系统 57. 仿真、智能机器人、机器博弈等，主持完 [12]KARP R M.Reducibility among combinatorial problems 成国家自然科学基金项目、863基金项 [Z].New York:Plenum Press,1972:85-103. 目、国家“八五"”、“九五”攻关课题13 [13]COOK S A.The complexity of theorem proving procedures 项，其中8项通过省、部级鉴定，获科技进步奖国家三等1 [C]//Proceedings of the Third Annual ACM Symposium 项，省部级科技进步奖多项。发表学术论文300余篇。 on Theory of Computing.New York,USA,1971:151-158

参考文献： ［１］ＳＩＰＳＥＲ Ｍ． Ｉｎｔｒｏｄｕｃｔｉｏｎ ｔｏ ｔｈｅ ｔｈｅｏｒｙ ｏｆ ｃｏｍｐｕｔａｔｉｏｎ［Ｍ］． ２ｎｄ ｅｄ． Ｂｅｉｊｉｎｇ： Ｃｈｉｎａ Ｍａｃｈｉｎｅ Ｐｒｅｓｓ， ２００６： ２６５⁃３２３． ［２］ＤＡＳＧＵＰＴＡ Ｓ， ＰＡＰＡＤＩＭＩＴＲＩＯＵ Ｃ Ｈ， ＶＡＺＩ⁃ＲＡＮＩ Ｕ Ｖ． Ａｌｇｏｒｉｔｈｍ［Ｍ］． Ｎｅｗ Ｙｏｒｋ： ＭｃＧｒａｗ⁃Ｈｉｌｌ Ｓｃｉｅｎｃｅ ／ Ｅｎｇｉｎｅｅｒ⁃ ｉｎｇ ／ Ｍａｔｈ， ２００６： ２５７⁃２６４． ［３］ＰＡＰＡＤＩＭＩＴＲＩＯＵ Ｃ． Ｃｏｍｐｕｔａｔｉｏｎａｌ ｃｏｍｐｌｅｘｉｔｙ［Ｍ］． Ｒｅａｄ⁃ ｉｎｇ， Ｍａｓｓａｃｈｕｓｅｔｔｓ： Ａｄｄｉｓｏｎ⁃Ｗｅｓｌｅｙ， １９９４： ４９１⁃４９３． ［４］朱一清．可计算性与计算复杂性［Ｍ］．北京：国防工业出 版社，２００６： ４４⁃４５． ［５］堵丁柱．计算复杂性导论［Ｍ］．北京：高等教育出版社， ２０００： ２１⁃２２． ［６］ＡＲＯＲＡ Ｓ， ＢＡＲＡＫ Ｂ． Ｃｏｍｐｕｔａｔｉｏｎａｌ ｃｏｍｐｌｅｘｉｔｙ［Ｍ］． Ｎｅｗ Ｙｏｒｋ： Ｃａｍｂｒｉｄｇｅ Ｕｎｉｖｅｒｓｉｔｙ Ｐｒｅｓｓ， ２００７： ２４⁃８５． ［７］ 陈志平，徐宗本． 计算机数学———计算复杂性理论与 ＮＰＣ、ＮＰ 难问题的求解［ Ｍ］．北京：科学出版社，２００１： ８１⁃８３． ［８］ＮＰ ［ ＤＢ／ ＯＬ］． ［ ２０１３⁃１０⁃１７］． ｈｔｔｐ： ／ ／ ｚｈ． ｗｉｋｉｐｅｄｉａ． ｏｒ⁃ｇ ／ ｗｉｋｉ ／ ＮＰ． ［９］ＣＯＰＲＩＭＥ［ＤＢ／ ＯＬ］． ［ ２０１３⁃１０⁃１７］． ｈｔｔｐ： ／ ／ ｚｈ． ｗｉｋｉｐｅｄ⁃ｉａ． ｏｒｇ ／ ｗｉｋｉ ／ ＣＯＰＲＩＭＥ． ［１０］ＧＲＡＨＡＭ Ｒ Ｌ， ＫＮＵＴＨ Ｄ Ｅ， ＰＡＴＡＳＨＮＩＫ Ｏ． Ｃｏｎｃｒｅｔｅ ｍａｔｈｅｍａｔｉｃｓ［Ｍ］． Ｍａｓｓａｃｈｕｓｅｔｔｓ： Ａｄｄｉｓｏｎ⁃Ｗｅｓｌｅｙ， １９８９： １０７⁃１１０． ［１１］ ＨＯＮＳＢＥＲＧＥＲ Ｒ． Ｍａｔｈｅｍａｔｉｃａｌ ｇｅｍｓ ＩＩ［Ｍ］． Ｗａｓｈｉｎｇｔｏｎ， ＤＣ： Ｔｈｅ Ｍａｔｈｅｍａｔｉｃａｌ Ａｓｓｏｃｉａｔｉｏｎ ｏｆ Ａｍｅｒｉｃａ， １９７６： ５４⁃ ５７． ［１２］ ＫＡＲＰ Ｒ Ｍ． Ｒｅｄｕｃｉｂｉｌｉｔｙ ａｍｏｎｇ ｃｏｍｂｉｎａｔｏｒｉａｌ ｐｒｏｂｌｅｍｓ ［Ｚ］． Ｎｅｗ Ｙｏｒｋ： Ｐｌｅｎｕｍ Ｐｒｅｓｓ， １９７２： ８５⁃１０３． ［１３］ＣＯＯＫ Ｓ Ａ． Ｔｈｅ ｃｏｍｐｌｅｘｉｔｙ ｏｆ ｔｈｅｏｒｅｍ ｐｒｏｖｉｎｇ ｐｒｏｃｅｄｕｒｅｓ ［Ｃ］ ／ ／ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ Ｔｈｉｒｄ Ａｎｎｕａｌ ＡＣＭ Ｓｙｍｐｏｓｉｕｍ ｏｎ Ｔｈｅｏｒｙ ｏｆ Ｃｏｍｐｕｔｉｎｇ． Ｎｅｗ Ｙｏｒｋ， ＵＳＡ， １９７１： １５１⁃１５８． ［１４］ＺＨＡＮＧ Ｌｉｎｔａｏ． Ｓｅａｒｃｈｉｎｇ ｆｏｒ ｔｒｕｔｈ： ｔｅｃｈｎｉｑｕｅｓ ｆｏｒ ｓａｔｉｓｆｉ⁃ ａｂｉｌｉｔｙ ｏｆ ｂｏｏｌｅａｎ ｆｏｒｍｕｌａｓ［Ｄ］． Ｐｒｉｎｃｅｔｏｎ： Ｐｒｉｎｃｅｔｏｎ Ｕｎｉ⁃ ｖｅｒｓｉｔｙ， ２００３： １０⁃１４． ［１５］ ＣＯＲＭＥＮ Ｔ Ｈ， ＬＥＩＳＥＲＳＯＮ Ｃ Ｈ， ＲＩＶＥＳＴ Ｒ Ｌ， ｅｔ ａｌ． Ｉｎｔｒｏｄｕｃｔｉｏｎ ｔｏ ａｌｇｏｒｉｔｈｍｓ［Ｍ］． ２ｎｄ ｅｄ． Ｃａｍｂｒｉｄｇｅ， Ｍａｓ⁃ ｓａｃｈｕｓｅｔｔｓ：ＭＩＴ Ｐｒｅｓｓ， ２００９： １１０８⁃１１１０． ［１６］ＶＥＲＴＥＸ ＣＯＶＥＲ ［ＤＢ／ ＯＬ］． ［ ２０１３⁃１０⁃１９］． ｈｔｔｐ： ／ ／ ｚｈ． ｗｉｋｉｐｅｄｉａ．ｏｒｇ ／ ｗｉｋｉ ／ ＶＥＲＴＥＸ ＣＯＶＥＲ． ［１７］ ＳＴＯＣＫＭＥＹＥＲ Ｌ Ｊ， ＣＨＡＮＤＲＡ Ａ Ｋ． Ｐｒｏｖａｂｌｙ ｄｉｆｆｉｃｕｌｔ ｃｏｍｂｉｎａｔｏｒｉａｌ ｇａｍｅｓ ［ Ｊ］． ＳＩＡＭ Ｊ Ｃｏｍｐｕｆ， １９７９ ８ （ ２）： １５１⁃１７４． ［１８］罗森．离散数学及其应用［Ｍ］．北京：机械工业出版社， ２０１１： ２１⁃３０． ［１９］ ＰＳＰＡＣＥ ［ ＤＢ／ ＯＬ］． ［ ２０１３⁃１０⁃２０］． ｈｔｔｐ： ／ ／ ｚｈ． ｗｉｋｉｐｅｄｉａ． ｏｒｇ ／ ｗｉｋｉ ／ ＰＳＰＡＣＥ． ［ ２０］ ＳＡＶＩＴＣＨ Ｗ Ｊ． Ｒｅｌａｔｉｏｎｓｈｉｐｓ ｂｅｔｗｅｅｎ ｎｏｎｄｅｔｅｒｍｉｎｉｓｔｉｃ ａｎｄ ｄｅｔｅｒｍｉｎｉｓｔｉｃ ｔａｐｅ ｃｏｍｐｌｅｘｉｔｉｅｓ［ Ｊ］． Ｊｏｕｒｎａｌ ｏｆ Ｃｏｍ⁃ ｐｕｔｅｒ ａｎｄ Ｓｙｓｔｅｍ Ｓｃｉｅｎｃｅｓ， １９７０ ４（２）： １７７⁃１９２． 作者简介： 高强，男，１９８０ 年生，讲师，博士研 究生，主要研究方向为机器博弈、计算 复杂性理论。 徐心和，男，１９４０ 年生，教授，博士 生导师，中国人工智能学会常务理事， 主要研究方向为控制理论与应用、系统 仿真、智能机器人、机器博弈等，主持完 成国家自然科学基金项目、８６３ 基金项 目、国家“八五”、“九五” 攻关课题 １３ 项，其中 ８ 项通过省、部级鉴定，获科技进步奖国家三等 １ 项，省部级科技进步奖多项。 发表学术论文 ３００ 余篇。 第 ５ 期 高强，等：时间复杂性和空间复杂性研究 ·５３５·