NP完全理论初步

Posted on
  • 下列每对问题, 一个是可用多项式时间算法解决的, 一个是NP完全问题
    • 最短和最长简单路径
    • 欧拉回路和哈密顿圈
    • 2-CNF可满足性问题和3-CNF可满足性问题
  • 证书: 如哈密顿圈问题中的|V|个顶点序列, 3-CNF可满足性问题中的一组变量的赋值
  • 可被证明: 已知一个问题的证书, 可以证明此问题在该输入规模下能在多项式时间内解决
  • 所有P类问题同时也是NP问题, P类问题不用任何证书就可以在多项式时间内解决
  • 判定问题和最优化问题
  • 归约:
    • 某一特定问题的输入为该问题的实例.
    • 对于一个判定问题A, 假设有另一个不同的判定问题B, 我们知道如果在多项式时间内解决
    • 有一个过程, 可将A的任意实例$\alpha$转化为B的具有以下特征的某个实例$\beta$:
      • 转换操作需要多项式时间
      • 两个实例的解是相同的, $\alpha$的解为”是”当且仅当$\beta$的解为”是”
      • 称这一过程为多项式时间归约算法
    • 一种多项式时间解决A的方法:
      • 给定问题A的实例$\alpha$, 利用多项式时间归约算法, 将他转化为问题B的一个实例$\beta$
      • 在实例$\beta$上, 运行B的多项式时间判定算法
      • 将$\beta$的解作为$\alpha$的解
  • 相反的, 利用多项式时间归约, 说明一个问题是NP完全的:
    • 假设有一个判定问题A, 已知它不可能存在多项式时间算法
    • 假设有一个多项式时间的归约, 将A的一个实例转化为一个B的实例
    • 如果B存在多项式时间算法, 那么A也存在多项式时间算法, 矛盾
    • 类似的, 可以在问题A是NP完全的假设下, 证明问题B是NP完全的
  • 第一个NP完全问题
    • 电路可满足性问题

多项式时间

  • 抽象问题Q: 在问题实例集合I和问题解集合S上的一个二元关系
  • 编码: 抽象对象集合S的编码是从S到二进制串集合的映射e
  • 具体问题: 以二进制串集合为实例集的问题
  • 多项式时间可解: 对于常数k, 存在一个能在$O(n^k)$时间内求解出某具体问题的算法
  • 复杂类P: 在多项式时间内可解的具体判定问题的集合
  • 编码会影响算法运行时间
  • 对于某个问题的实例集I, 如果存在两个多项式时间可计算的函数$f_{12}$和$f_{21}$满足对于任意$i\in I$, 有$f_{12}(e_1(i)) = e_2(i)$, 且$f_{21}(e_2(i)) = e_1(i)$, 那么这两种编码$e_1$和$e_2$是多项式相关的.
  • Q是顶一个在一个实例集I上的一个抽象判定问题, $e_1$和$e_2$是I上多项式相关的编码, 则$e_1(Q)\in P$当且仅当$e_2(Q)\in P$
  • 形式语言体系:
    • 字母表, 语言, 交, 并, 补, 连结, …
    • 闭包$L^* = \{\epsilon \}\cup L \cup L^2 \cup L^3 \cup \cdots$, 其中$L^k$是L与其自身进行k次连结运算后得到的语言
    • 复杂类P的另一种定义: $P =\{L \subseteq \{0, 1\}^*: 存在一个算法A, 可以在多项式时间内判定L\}$
    • $P = \{L: L被一个多项式时间算法所接受 \}$

多项式时间的验证

  • 验证算法:
    • 含两个自变量的算法A, 其中一个自变量是普通输入串x, 另一个是称为证书的二进制串y.
    • 如果存在一个证书y满足$A(x, y)= 1$, 则该含两个自变量的算法A验证了输入串x.
    • 由一个验证算法A锁验证的语言是: $L=\{x\in \{0, 1\}^: 存在y\in \{0,1\}^, 满足A(x, y)=1\}$
    • 如果对任意串$x\in L$, 都存在一个证书y, 且算法A可以用y来证明$x\in L$, 则算法A就验证了语言L.

复杂类NP

  • 复杂类NP是能被一个多项式时间算法验证的语言类
  • 一个语言$L\in NP$, 当且仅当存在一个2输入的多项式时间算法A和常数c, 满足
    $L = \{x\in \{0,1\}^* : 存在一个证书y, |y|= O(|x|^c), 满足A(x,y)=1\}$
  • $P\subseteq NP$

NP完全性与可归约性

  • 如果任何一个NP完全问题能在多项式时间内得到解决, 那么NP中每一个问题都存在一个多项式时间解, 即P = NP
  • HAM-CYCLE为NP完全问题

可归约性

  • 问题Q可以被归约为另一个问题Q’: Q的任何实例都可以被”容易地重新描述”为Q’的实例, 而Q’的实例的解也是Q的实例的解
  • Q可以转化为Q’, 则Q并不比Q’更难解决
  • 定义: 语言$L_1$在多项式时间内可以归约为语言$L_2$, 记作$L_1 \le_p L_2$, 如果存在一个多项式时间可计算的函数$f: \{0, 1\}^* \to \{0, 1\}^*$, 满足对于所有的$x\in\{0, 1\}^*$, $x\in L_1$当且仅当$f(x) \in L_2 $, 则称函数f为归约函数, 计算f的多项式时间算法F为归约算法
  • 如果$L_1, L_2\subseteq \{0,1\}^*$满足$L_1\le_p L_2$, 则$L_2\in P$蕴含$L_1\in P$

NP完全性

  • 语言$L\in \{0,1\}^$是*NP完全的, 如果:
    • $L\in NP$
    • 对每一个$L’ \in NP$, 有$L’\le_p L$
  • 如果语言L满足性质2, 但不满足性质1, 则称L是NP难度的
  • NPC为NP完全语言类
  • 电路可满足性问题CIRCUIT-SAT = {\: C是一个可满足的不二组合电路}是NP完全的

NP完全性证明

  • 如果语言L是一种满足对任意$L’ \in NPC$都有$L’\le_P L$的语言, 则L是NP难度的. 此外如果$L\in NP$, 则$L \in NPC$
  • 证明一种语言L是NP完全语言的方法:
    • 证明$L\in NP$
    • 选取一种一致的NP完全语言L’
    • 描述一种可计算函数$f(x)$的算法, 其中$f$可将L’中每一个实例$x\in \{0,1\}^*$映射为L中的实例$f(x)$
    • 证明函数$f$满足对于所有的$x\in \{0,1\}^*$都有 $x\in L’$当且仅当$f(x)\in L$
    • 证明计算函数$f$的算法具有多项式运行时间

公式可满足性

  • 布尔公式可满足性问题是NP完全的:
    • $SAT\in NP$:
      • 对于输入$\phi$, 由它的一个可满足性赋值组成的证书可以在多项式时间内得到验证
      • 方法为: 将公式中每个变量替换为其对应的值, 再求解
    • CIRCUIT-SAT$\le_P$ SAT:
      • 给定一个电路C, 可以直接在多项式时间内产生一个公式: 电路输出变量与描述每个门的操作的子句合取式的”与”
      • 如果电路C有一个可满足性复制, 那么电路的每条线路都有一个良定义的值且输出为1, 赋值后$\phi$的每个子句的值为1, 合取值也为1. 反之存在一个赋值使$\phi = 1$, 则类似可证C可满足

3-CNF可满足性

  • 3合取范式形式的布尔公式的可满足性问题是NP完全的
    • 易证3-CNF-SAT $\in$ NP
    • SAT $\le_P$ 3-CNF-SAT:
    • 为输入公式$\phi$构造一棵二叉”语法分析”树, 将蚊子作为树叶, 连接词作为内部顶点, 从而把二叉语法分析树视作计算该函数的一个电路
    • 为每个内部顶点的输出引入一个变量$y_i$, 把$\phi$ 改写为根变量与描述每个顶点操作的子句的合取的与, 每一个子句至多3个文字.
    • 把所有子句转换为合取范式, 使子句都是CNF且至多包含3个文字
    • 使用辅助变量p和q把每个CNF转为3-CNF

NP完全问题

团问题

  • 证明3-CNF-SAT$\le_P$CLIQUE
    • 设$\phi = C_1 \land C_2 \land \cdots \land C_k$是3-CNF形式中一个有k个子句的布尔公式
    • 构造图G: 对$\phi$中的每个字句$G_r = (l_1^r \lor l_2^r \lor l_3^r)$, 把3个顶点$v_1^r, v_2^r, v_3^r$三元组放入V中.如果
      • $v_i^r$和$v_j^s$处在不同的三元组中, 即$r\ne s$
      • 他们相应的文字是一致的, 即$l_i^r$不是$l_j^s$的非
        则用一条边连接顶点$v_i^r$和$v_j^s$
    • 假设$\phi$有一个可满足性复制, 那么每个字句至少有一个文字$l_i^r$, 赋值为1, 对应顶点构成集合$V’$, 为团.
    • 反之亦然

顶点覆盖问题

  • VERTEX-COVER = {(G, k): 图G有一个规模为k的顶点覆盖}
  • CLIQUE $\le_P$ VERTEX-COVER
    • 包含团V’的无向图G, $\overline G$包含顶点覆盖V - V’

哈密顿回路问题

  • VERTEX-COVER $\le_P$ HAM-CYCLE

旅行商问题

  • TSP = {(G, c, k): G = (V, E)是一个完全图, c是V $\times$ V $\to$ Z的一个函数, $k\in Z$, G中包含一个最大花费为k的旅行回路}
  • HAM-CYCLE $\le_P$ TSP
    • G(V, E)是HAM-CYCLE的一个实例, , 构造TSP如下:
      • 完全图G’ = (V, E’)
      • 费用函数c(i, j) = 1若$(i, j) \in E$, 否则为0

子集和问题

  • subset-sum problem
  • SUBSET-SUM =$\{(s,t): \text{存在一个子集}S’ \subseteq S,\text{使得} = \sum_{s\in S’}s\}$
  • 3-CNF-SAT $\le_P$ SUBSET-SUM: