算法设计与分析.08.NP 完全性理论 (3)

NP 完全性理论 (3)

• intractability

P与NP

P问题

• 判定性问题（decision problem）

• 算法 \(A\) 是多项式时间的，\(A(s)\) 能够在小于等于 \(p(\vert{s}\vert)\) 步骤内完成
  • \(p(\cdot)\) 是多项式
• P 问题：存在多项式算法的判定性问题
• 例子（质数）

NP问题

• certifier：验证器
• 算法 \(C(t,s)\) 是问题 \(X\) 的验证器
  • \(\forall s\in X\Leftrightarrow \exist t\) 使得 \(C(s,t)=\text{yes}\)
• NP 问题：存在多项式时间验证器的判定算法
  • \(C(t,s)\) 是多项式时间算法
  • \(t\) 是多项式时间的大小，\(\vert{t}\vert\le p(\vert{s}\vert)\)，\(p(\cdot)\) 是多项式
• 多项式是时间可验证的，如果存在一个解，那么是多项式时间可验证的
• 例子（质数）

• SAT \(\in\) NP，3-SAT \(\in\) NP
  • 代入判定即可

• 哈密顿回路 \(\in\) NP
• NP：Nondeterministic polynomial time
  • 非确定性的，多项式时间可验证的算法
  • 如果找到证据 \(t\)，则就可以在多项式时间验证
  • 但是找到 \(t\) 的时间不确定

P-NP-EXP

• P：Decision problems for which there exists a poly-time algorithm.
• NP：Decision problems for which there exists a poly-time certifier.
• EXP：Decision problems for which there exists an exponential-time algorithm.

关系

• P \(\subseteq\) NP
  • \(C(s,t)=A(s)\) 即可
  • \(A(s)\) 是多项式时间的算法
• NP \(\subseteq\) EXP
  • \(\vert{t}\vert\le p(s)\)
  • 枚举所有的 \(t\)，每一个 \(t\) 可以在多项式时间内验证
  • 如果有一个 \(t\) 返回 yes，则返回 yes
• 3-SAT \(\in\) EXP
  • 枚举 \(2^n\) 种赋值
• 推测（conjecture）：3-SAT \(\notin\) NP

P=NP?

• 一般观点：no

NPC

• NP complete

多项式归约

• Cook 归约：多次调用
  • 多项式时间归约
  • polynomial (Cook) reduction
• Karp 归约：一次调用
  • 多项式时间变换
  • polynomial (Karp) transformation

• 在描述中，我们混用他们，因为在问题的难易程度上，都表示 X 不比 Y 难

NPC

• NP complete
• \(Y\in NPC\)
  • \(Y\in NP\)
  • \(\forall X\in NP,X\le_{p} Y\)
• 如果 \(Y \in NPC\)，此时 \(Y\in P\Leftrightarrow P=NP\)
  • \(\Rightarrow\)：

\[ \begin{array}{c} \forall X\in NP,X\le_{p}Y\Rightarrow X\in P\\ NP\subseteq P \end{array} \]

• 第一个被证明的 NPC 问题
• SAT \(\in\) NPC

证明 NPC

• 如何证明 \(Y\in NPC\)
  • \(Y\in NP\)
  • 找到 \(X\in NPC\)
  • 证明 \(X\le_{p} Y\)
• 传递性

NPC 问题

• Cook-Levin / Karp

• 《Computers and Intractability》
  • Garey and Johnson

co-NP

• NP 问题的补问题
• Set / Un-Set
  • Set：判定一个 CNF 可满足
  • Un-Set：判定一个 CNF 不可满足
• 哈密顿回路 / 不存在哈密顿回路
• Set \(\in\) NPC，Set \(\equiv_{p}\) Un-Set，但是 Un-Set \(\notin\) NP
  • 不是多项式时间可验证的
• 问题 \(X\) 的补问题 \(\overline{X}\)：和 \(X\) 相同，只是把回答互换了（yes/no 互换）
• co-NP：NP 问题的补问题
• NP=co-NP ?
  • 一般认为：no

定理

\[ NP\ne co-NP\Rightarrow P\ne NP \]

• P 问题的补问题还是 P 问题
• 如果 \(P=NP\)，那么 NP 问题的补问题还是 NP 的，于是 \(NP=co-NP\)

NP-coNP

• 二部图的匹配问题
• 给定一个二部图，问是否存在完美匹配？
  • yes：存在匹配
  • no：存在一个节点子集 S，满足 \(\vert\text{neighbor}(S)\vert\le\vert{S}\vert\)
• 最大流——最小割
  • 最大流 \(\ge k\) ？（NP）
  • 最大流 \(\le k-1\)？（co-NP）
    • 最小割 \(\le k-1\) （NP）
• 好的形式化能够让问题变简单
• 观察

\[ P\subseteq NP\cap co-NP \]

• \(P=NP\cap co-NP\) ？
  • 没有统一意见

Linear programming

• 线性规划问题

\[ A\in\mathrm{R}^{m\times n},b\in\mathrm{R}^{m},c\in\mathrm{R}^{n},\alpha\in\mathrm{R} \]

• 是否存在 \(x\in\mathrm{R}^{n}\) 满足 \(Ax\le 0,x\ge 0,c^{T}x\ge\alpha\)
• 补问题
  • 如果有解，则 max=min

• 线性规划 \(\in NP \cap co-NP\)
  • [Gale–Kuhn–Tucker 1948]
• 线性规划 \(\in P\)
  • [Khachiyan 1979]

Primes

• primes \(\in NP\cap co-NP\)
  • [Pratt 1975]

• primes \(\in P\)
  • [Agrawal–Kayal–Saxena 2004]

质因子分解

• factorize：给定 x，找到 x 的质因数分解
• factor：给定 x、y，问 x 是否存在比 y 小的因数（非1）
• factor \(\equiv_{p}\) factorize
  • \(\le_{p}\)：找到因子分解，然后逐个过一遍就好
  • \(\ge_{p}\)：二分找到因子，除以这个因子继续重复这个步骤
• factor \(\in NP\cap co-NP\)
  • certificate：给定一个小于 \(y\) 的因子
  • disqualifier：给定质因数分解（都小于 \(y\)）
• factor \(\in\) P ？
  • 暂时未知
• RSA 加密算法：利用质数相乘容易，之因素分解难的性质
• 量子计算机：\(n\) bit 整数能够在 \(O(n^3)\) 时间按复杂度上计算
  • 引入了随机
  • 有一定错误概率
• P = BQP ?
  • BQP：bounded error quantum polynomial time

NP 难

• NP-complete（NP 完全）
  • A problem in NP such that every problem in NP poly-time reduces to it.
• NP-hard（NP 难）
  • A problem such that every problem in NP poly-time reduces to it.
  • 和 NPC 相比，不要求问题本身是 NP 的