《基本NP完全问题的证明》由会员分享，可在线阅读，更多相关《基本NP完全问题的证明（54页珍藏版）》请在金锄头文库上搜索。
1、1 5.6 基本 NP完全问题的证明 2 定理 1 三可满足问题 (3SAT)是 NP完全问题。 (证 ) 整个证明过程分成两步， 先证 3SAT NP， 再证明 SAT 3SAT 3SAT NP是显然的，因为很容易构造一不确定算法， 该算法第一阶段猜一个函数 f： U 真 , 假 。 3 然后，第二阶段检测公式 F的值， 这只需将公式 F中的所有因子 u及 u分别用 f(u)和 f(u)的补替代， 即用“真”或“假”替代， 再对逻辑式求值。 容易看出，第二阶段所需时间是 m和n的多项式 其中 m是集合 U的逻辑变量的个数， n是公式 F的项的个数。 4 SAT 3SAT就不那末明显了。 先构
2、造映射 g： SAT 3SAT 其中 SAT表示可满足性问题的实例之集合 3SAT表示三可满足性问题的实例的集合。 然后再证明 g是多项式转换 。 SAT的实例为 集合 U u1,u2, ,um 公式 F c1,c2, ,cn， 其中 ci (i 1， 2， ， n)是项。 以 U及 F为输入， g为 3SAT构造实例 U及 F如下所述 : 5 U = U U1 U2 Un F = C1 C2 Cn 其中 Cj 是项的集合，且每一项含三个因子 因此 F也是项的集合，所以 F是公式。 由上两式可见 : 逻辑变量集合 U增加一些变量， 再改写公式 F的每一项为项集合， 就得到三可满足问题的实例。
3、还需证明 F是可满足的充分必要条件为 F是可满足的。 6 为定义映射 g，只须说明如何构造Cj 及 Uj . 公式 F的项 Cj是因子的集合 Cj Z1， Z2， ， ZK 即 | Cj | K， Cj由 K个因子组成。 Cj 及 Uj的构成按 K的值 分四种情况讨论。 7 K l， Cj z1，则 Uj及 Cj构造为 Uj yj1, yj2 增加两个逻辑变量而已 Cj z1,yj1, yj2,z1, yj1,yj2 ,z1, yj1,yj2 , z1, yj1, yj2 即 Cj含四个项。 将 Cj一个项替换为四个项 . 注意 : 这四个项 穷尽 两个逻辑变量 yj1, yj2 的 四种情况
4、 8 K 2， Cj z1 ， z2，则 Uj yj 仅仅增加一个逻辑变量 Cj z1， z2， yj， z1， z2， yj 即 Cj含两项。 将 Cj一个项替换为两个项 . 注意 : 这两个项 穷尽 一个逻辑变量 yj 的 两种情况 9 K 3， Cj z1 ， z2 ， z3，则 Uj 不增加逻辑变量 Cj z1 ， z2 ， z3 即 Cj含一项。 10 K3， Cj z1,z2 , ,zk ，则 Uj yj1,yj2 ,y jk-3 , 增加 K - 3个逻辑变量 Cj z1,z2 ,yj1 , z3, yj1,yj2, z4, yj2,yj3, , z i-1, yji-3,yji
5、-2, z i , yji-2,yji-1, zi+1, yji-1,yji, , zk-2, yjk-4,yjk-3, zk-1,zk ,yjk-3 即 Cj含 (K一 2)项 , 比 | Uj |大 1。 若 K=4, 则含两项 . 若 K=4, 则增一个变量 第一项和最后一项各含两个 z(原变量 )和一个 y(新增变量 ). 其余各项含一个 z和两个 y(其中一个是因子的非 ) 11 显然，映射 g为 3SAT问题计算一个实例所需时间为 m和 n的多项式。 要增加 n个变量集合 , 对应 F中的 n个项 . 每个集合至多含 m-3个变量 , m为 U中因子的个数 要把 n个项改写为 n个
6、 项集合 每个集合至多含 m-2个项 , 每项有三个因子 . 12 现在证明如 F可满足 , 则 F也可满足 . 设 f： U 真 , 假 能使 F值为真。 因 U是 U的子集 , 只须证明 f可以扩展为 f： U 真 , 假 并使公式 F为真； 从而只要给诸 Uj的各逻辑变量赋值 保持 U的逻辑变量的赋值不变 , 并使 F为真即可 13 因集合 (U U) 中的逻辑变量被划分为集合 Uj ， Uj中的逻辑变量仅出现在相应的 Cj中 , 因此只须证明， 映射 f可以逐次扩展到各集合 Uj， 每次扩展使 Cj中的项的值都为真 14 同样分四种情况， K 1， 用数理逻辑的方法很容易证明 Cj和
7、Cj恒等， (P7) 即 Cj的值只与 z1有关， 因 f已经满足 Cj ， 则 f不论给 yj1, yj2赋什么值都能使 Cj满足。 15 K=2，同样可用数理逻辑 证明 Cj和 Cj恒等， 即 Cj的值只与 z1 ， z2有关， 因 f已经满足 Cj， 则不论 f给 yj赋什么值 , 都可使 Cj满足 16 K=3， (P9) Uj为空， 且 Cj只含一个项 , 就是 Cj, 已被 f满足。 Cj已经含三个因子 , 被 f赋值， 因此 f, 不用给任何新逻辑变量赋值。 17 K3， Cj= z1,z2 , ,zk ，因 f已满足 Cj， 此即 Cj的 K个因子中至少一个为真， 设 zi为真
8、， 按 i的值分三种情况 , 讨论如何扩展映射 f 18 () i为 1或 2，则令 yj1=yj2 = yjK-3=假 这使 Cj的每一项都为真。 ()如 i为 K 4或 K 3，则令 yj1=yj2 = yjK-3= 真 这也使 Cj的每一项都为真。 ()如 23， f满足 Cj，则只须证明 f使 z1， z2， ， zk 中至少有一个的值为真。用反证法 . 令 z1,z2 , ,zk 皆假 , 用“假”替代 Cj中的诸 z，再简化Cj 则 Cj等价为 25 Cj yj1 , yj1,yj2, yj2,yj3, , yji-3,yji-2, yji-2,yji-1, yji-1,yji,
9、, yjk-4,yjk-3, yjk-3 因 Cj被满足，则其各项之值皆“真”。 第一项之值为真，则必有 f(yj1)真 26 第二项 yj1,yj2等价于 yj2，其值为真，则必有 f(yj2)真 以此类推，由 Cj的倒数第二项为“真”知，必有 f(yjK-3) 真 但是由此确定的映射没能满足 Cj 因为 Cj的最后一项 yjk-3 必定为假，从而使 Cj值为假，即公式 F值为假，这与 f满足 F的假设矛盾。 27 这反证了 Cj中诸因子 z1,z2 , ,zk 至少有一个为真，这使 Cj值为真 . 因此映射 f使公式 F满足。证毕。 28 定理 2 顶点覆盖问题 (VC)是 NP完全问题。
10、 证明过程梗概 先定义 3SAT VC的多项式转换 f. 3SAT问题的实例为两个集合 U u1,u2, ,un F C1,C2, ,Cm 其中 Ci(i=1， 2， ， m)为含三个因子的项 由 3SAT的实例 , 映射 g构造 VC问题的实例有以下四步骤。 对每一个逻辑变量 ui U，构造子图 该子图由两个节点 ui ， ui 及一条边组成。 ui ui 30 对每一项 Ci F构造子图 vi2 vi1 vi3 以 Ci的三个因子为顶点 , 建造一个三角形 (有三条边 ) 31 对项 Ci vi1,vi2 ,vi3中每个因子 vij(j 1, 2, 3), 如 vij u (u U)， 则
11、连接节点 u(由 构造 )和节点 vij(由 构造 ) 如 vij u， 则连接节点 u和节点 vij 由以上三步得到 VC实例的图。 令 K=n+2m, n=|U| m=|F| 32 证明之前 , 给一个例子 . 33 设 3SAT问题有如下实例 U = u1， u2， u3， u4 F ul， u3， u4， ul， u2， u4， u2， u3， u4 ul ul u2 u2 u3 u3 u4 u4 K=10 显然实例是可满足的， f如上所示。 真 真 假 假 34 为证明本定理 ,须证明两件事 . VC NP 设 VC问题的实例 G = (V, E) 构造一不确定算法，该算法第一阶段猜
12、一个 V V(V 是 V的子集 ,且 |V|=K) 第二阶段检测 V 是否为 G的 K覆盖 . 这阶段的时间复杂度是多项式的 . 所以 VC问题可由多项式时间不确定算法解决 因此 ,VC NP 35 前面定义的映射 g是从 3SAT到 VC的多项式转换。 g的 四步骤的时间复杂度都是多项式的 所以 g的复杂度也是多项式的 下面证明 3SAT的实例可满足的充分必要条件是 : 它在 VC的像实例有 K覆盖 . 36 先设 3SAT问题的实例可满足 ,欲证明其在 VC的像实例有 K覆盖 存在映射 f, 给逻辑变量集合 U的各个 u赋值 , 使得 F的所有项 C1,C2, ,Cm 的值均为真 . 构造 VC的像实例的 K覆盖如下 . nts
