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