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