算法设计与分析.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 的