第七章 NP问题选讲 邹权（博士） 计算机科学系
提要 7.1 概念 7.2 规约 7.3 最大独立集问题
7.1 概念 判定问题 P是所有可在多项式时间内用确定算法求解的判定问题的集合。 NP问题是所有可用多项式时间算法验证其猜测准确性的判定问题的集合。 P NP P = NP ?
多项式时间规约 NP完全问题，满足： 问题A能够多项式时间规约到B 说明：B比A难！ 该问题是NP问题 NP-hard P NPC
7.2 规约 3-CNF可满足性问题 CNF（合取范式）：如果一个布尔公式是一些子句的合取（与），而且子句是一个文字或多个文字的析取（或），则该公式是CNF。 如果CNF中每个子句都有且只有3个不同的文字，则该公式称为3-CNF。 例：(x1 ¬x1 ¬x2) (x3 x2 x4) (¬x1 ¬x3 ¬x4)
7.2 规约 最大团问题 顶点覆盖问题 对于无向图G，一个团即图G的一个完全子图 最大团问题即是否可以找出一个团，使得其包含的顶点个数大于k 对于无向图G=(V,E)，是否可以找出子集V’，使得如果边(u,v) ∈E，则u ∈V’或v ∈V’，且|V’|<k
已知3-CNF可满足问题是一个NPC问题，试证明最大团问题也是NPC问题 为3-CNF φ构造一个图G。 然后欲证3-CNF φ可满足当且仅当图G有一个大小为k的团。 多项式规约说明：如果最大团问题可以多项式时间解决，那么3-CNF亦可以。也就是说：最大团不会比3-CNF容易！
已知最大团问题是一个NPC问题，试证明顶点覆盖问题也是NPC问题 为最大团的图G构造一个图G’ 然后欲证图G有一个大小为k的团当且仅当图G’ 有一个大小为|V|-k的顶点覆盖 多项式规约说明：顶点覆盖不会比最大团问题容易！ 如果最大团是NPC，顶点覆盖也是NPC。
CircuitSAT SAT 3-CNF-SAT Clique VertexCover SubsetSum HamCycle TSP GraphColoring SetCover Partition BinPacking ParallelScheduling Knapsack StripPacking
对比 以往的转化 本章的转化（多项式规约） 欲解决问题A，将其转化为较简单的问题B，然后解决B，从而解决A 欲证明B不可解，找一个不可解（NP完全）的问题A，将A多项式规约到B，从而说明B比A难，B也不可解
7.3 最大独立集问题 问题 NP完全性证明 解决办法 应用 对于无向图G=(V,E)，是否可以找出顶点个数大于k的子集V’，使得V‘中没有任何边 NP完全性证明 顶点覆盖中顶点的补集即独立集 解决办法 Hopfield神经网络 应用 RNA二级结构预测
输入：RNA序列 GGGCGACUAGCUCAAGUGGUAGAGCGCUCGCUUAGCAUGCGAGAGGUACGGGGAUCGAUACCCCGGUCGUCCA 输出：配对关系 目标：尽量多的碱基配对 RNA二级结构预测问题的输入是RNA序列,
参考文献 Quan Zou, Tuo Zhao, Yang Liu, Maozu Guo. Predicting RNA secondary structure based on the class information and Hopfield network. Computers in Biology and Medicine. 2009,39(3):206-214 刘琦，张引，叶修梓，俞荣栋. 基于离散 Hopfield网络求解极大独立集的茎区选择算法以及在RNA二级结构预测中的应用. 计算机学报. 2008,31(1):51-58 Y. Takefuji, L. Chen, K. Lee, J. Huffman. Parallel Algorithms For Finding A Near-Maximum Independent Set of A Circle Graph. IEEE Transaction On Neural Networks. 1990,1(3):263-267