[计算理论] P NP NPC NP

理论] P NP NPC NP"/>

[计算理论] P NP NPC NP

可计算性基本概念

可计算性理论：研究计算的一般性质的数学理论，它通过建立计算的数学模型（例如抽象计算机），精确区分哪些是可计算的，哪些是不可计算的。
Church-Turing论题：若一函数在某个合理的计算模型上可计算，则它在图灵机上也是可计算的。

不可计算性：很多问题和函数是无法用具有有穷描述的过程完成计算

可计算性：是指一个实际问题是否可以使用计算机来解决。
即可解释为：可计算函数与之对应的问题是可计算的（该问题具有可计算性和可解性）
(注: 是否所有问题都能用计算机解决？否！并非所有问题都是计算机可解的, 其相应的函数是不可计算的.

可计算性问题：其计算复杂性的度量方式

• 多项式时间算法：设n是输入的size，k是某个常数，其最坏情况下的运行时间是 O( n k n^k nk) 的算法。
• 超多项式时间算法：问题可解，但并非对任意的常数k其算法的时间均是 O( n k n^k nk) 。

不可计算性问题：无论使用何种计算机，无论使用多少时间都无法解决的问题。例如，图灵停机问题 (停机问题：能否写一个程序正确判定输入给它的任何一个程序是否会停机. 理论上可证明这个判定停机的程序并不存在, 所以停机问题原理上不可解, 图灵采用康托对角化方法证明停机问题的不可判定性, 可以参考图灵在1936年的论文.pdf

图灵机

依据控制器的状态和读写头所读字符，决定执行以下3个操作之一、之二或全部：
1）改变有限状态控制器中的状态；
2）读写头在相应的方格中写一符号；
3）读写头左、右移一格或不动。

确定型图灵机DTM：若对任一个状态和符号，要执行的动作都是唯一的
非确定型图灵机NTM：若执行的动作是有穷多个可供选择

P/NP/NPC类问题

形式语言

字母表：字母表∑是符号的有限集
语言 L：字母表∑上的语言L是由表中符号组成的串的任意集合， ε表示空串， Φ表示空语言
闭包∑*： ∑上所有串构成的语言， ∑上每个语言均是∑的一个子集
接受/拒绝串：设输入x∈{0, 1}, 若算法输出 A(x) = 1，则称算法A接受串x；若 A(x) = 0，则算法A拒绝串x。
接受语言：算法A接受的串的集合，即 L = { x∈ {0, 1}* : A(x) = 1 }
算法A接受语言L：∀x∈L，A(x)=1
判定语言L: 若算法A接受L中的每个串，拒绝每个不在L中的串，则称L是由A判定的语言
算法A判定语言L: ∀x ∈L , A(x)=1; ∀x ∉ L , A(x)=0;
多项式时间接受的语言L: 若存在某个常数k，对任意长度为n的串 x∈L, 算法A在O( n k n^k nk)时间内接受x， 则称L是算法A在多项式时间内接受的语言。
多项式时间判定的语言L: 若存在某个常数k，对任意长度为n的串 x∈ {0, 1 }*, 算法A可在O( n k n^k nk)时间内正确地判定是否有x ∈ L， 则称L是算法A在多项式时间内可判定的语言。

P类问题

一类问题的集合，对其中的任一问题，都存在一个确定型图灵机M和一个多项式p，对于该问题的任何（编码）长度为n的实例，M都能在p(n)步内，给出对该实例的回答
形式化定义：P={ L：L是一个能在多项式时间内被一台DTM所接受的语言}
非形式定义：P是所有用确定性算法在多项式时间内可解的(判定)问题的集合

NP类问题

一类问题的集合，对其中的任一问题，都存在一个非确定型图灵机M和一个多项式p，对于该问题的任何（编码）长度为n的实例，M都能在p(n)步内，给出对该实例的回答。
形式化定义： NP={ L：L是一个能在多项式时间内被一台NTM所接受的语言}
非形式定义：NP是所有用非确定性算法在多项式时间内可解的(判定)问题的集合
(若NTM在每一步都恰有2步可供选择，则回答实例需考察 2 p ( n ) 2^{p(n)} 2p(n)种不同的可能性。

解释: 非确定性算法或者说非确定型图灵机可以直观理解为无限核的分布式算法, 对于每一个计算步骤的n种可能性都可以同时执行, 最后可以在多项式时间内求解NP问题; 相对于确定性算法即每一个步骤只能一次计算一种可能性, 所以需要指数时间才能求解.
另外对于某些指数时间才能求解的可计算问题, 量子计算的算法可以实现多项式时间求解, 因为量子计算本质上类似于一种概率/并行算法(非严谨, 只是类比, 理论上还没证明量子计算可以多项式时间解决任意NP类问题

NP问题求解可分为两个阶段：
猜测阶段: 对规模为n的输入实例x，产生一个输出y。通常是用多项式时间的非确定算法产生解y，可以通过增加1条非确定性选择语句实现之：choice( S )： 任意选择集合S的1个元素。对同一个实例x，下次输出的解就不一定是y。
验证阶段: 检验y是否满足解的形式，是否是问题的解？验证阶段是使用多项式时间的确定性算法。
(注: 有些难解问题不能在多项式时间内验证，因此并非所有的难解问题都属于NP类的！如汉诺塔问题，验证其解需要 2 n 2^n 2n步

非确定的判定算法
输出0: 当且仅当没有一种选择可导致success
输出1: 当且仅当至少存在一种选择导致success

非确定算法例子: 在数组A[1…n] ( n≥1 )中查找x，即确定 j 使A[j]=x，若x∉A, 则j=0。

Search（A）{j = choice( A ); // 并行判断 A 中所有元素是否与 x 相同if A[j] == x then {print( j ); // success 若 x ∈ A，必定成功}print(0); // failure 当且仅当A中没有j满足A[j]=x
}        

时间复杂度：O(1)

验证算法
算法A有2个参数：x是待验证的输入串，y是称为证书的二进制串。算法A验证了输入串x是指：若 ∀x∈L，∃证书y，使得A(x, y)=1

多项式时间验证
若存在一个多项式时间算法A和常数c，满足：L = { x∈{0,1}* : ∃证书y，|y| = O( ∣ x ∣ c |x|^c ∣x∣c) 满足 A(x,y)=1 } 则称算法A在多项式时间内验证了语言L。

由此可以给出NP类问题的定义: 多式时间内可验证的问题（指验证其解的正确性）

另一种定义
定理：语言L可在多项式时间内被非确定性地接受，当且仅当L可在多项式时间内被确定性地验证
非形式地：多式时间内可验证的问题即为NP问题

两个等价定义
NP= {NDTM能在多项式时间内接受的语言类}
NP= {DTM能在多项式时间内验证的语言类}

NPC类问题

多一归约: 假设L1和L2是两个判定问题，f 将L1的每个实例 I 变换成L2的实例 f(I)。若对L1的每个实例 I，I的答案为“yes”当且仅当 f(I) 是L2的答案为“yes”的实例，即：∀I，I是L1输出“yes“的实例 ⇔ f(I) 是L2输出”yes“的实例
则称 f 是从L1到L2的多一归约，记作： L 1 ≤ m L 2 L1≤_mL2 L1≤m​L2（传递关系, 而且满足自反性和传递性
直观解释：将求解L1的问题转换为求解L2的问题，而问题L1不会难于L2， L2至少比 L1难

多项式时间多一归约：若 f 是多项式时间可计算，则上述归约称为多项式时间多一归约，也称多项式时间变换, 记为 L 1 ≤ m p L 2 L1 \leq_m^p L2 L1≤mp​L2

NPC问题：对于一个(判定性)问题q，若满足两个条件
(1) q∈NP
(2) NP中任一问题均可多项式时间多一归约到 q
则称问题q为NP-完全的(NP-complete，NPC)

(SAT问题为第一个NPC问题

NP-hard类问题

NP-hard问题：若问题 q 仅满足条件(2)而不一定满足条件(1)，则问题q称为NP-难的(NP-hard，NPH)。显然：NPC⊆NP-hard
解释: 有一类问题已被证明属于NP-hard但不属于NP，即这类问题至少与NP-complete一样难，但这类问题又不属于NP（自然也不属于NPC）。例如围棋的必胜下法就是一个NP-hard的问题

NPC和NP-hard关系
(1) NP-hard问题至少跟NPC问题一样难。
(2) NPC问题肯定是NP-hard的，但反之不一定. 例：停机问题是NP-hard而非NPC的

P、NP、NPC和NP-hard之关系
NPC是NP中最难的问题，但是NP-hard至少与NPC一样难

证明问题属于NPC/NPH的思路:
对于一个问题q, 如果要证 q 是NPH的，只要找到1个已知的NPC或NPH问题q’，然后将q’多项式归约到q即可。
若还能验证q ∊NP，则证明 q 是NPC的

总结

整个计算机科学的大厦就建立在图灵机可计算理论和计算复杂性理论的基础上
P=NP难题是七大千禧难题之首, 这个问题是著名计算机科学家(1982年图灵奖得主)斯蒂文·考克（StephenCook ）于1971年发现并提出的
第一个NPC问题SAT的贡献在于：只要能证明一个问题T属于NP且可将SAT归约到T，则T就是NPC的，为发现NPC奠定了基础。此后以SAT为基础，发现和证明了许多NPC问题，形成了一棵以SAT为根的NPC树。当该树的NPC问题中任何一个问题可归约到新问题时，新问题是NP-Hard的。

NPC问题的分类包括6类
1.包装问题：SET-PACKING，INDEPENDENT SET
2.覆盖问题：SET-COVER， VERTEX-COVER
3.约束满足问题：SAT， 3-SAT
4.序列问题：HAMILTONIAN-CYCLE， TSP
5.分区问题：3D-MATCHING, 3-COLOR
6.数值问题：SUBSET-SUM， KNAPSACK

只要找到一个NPC或NPH问题的多项式算法，相当于所有NP中的问题多项式时间可解，则P=NP. 那么所有已知软件的性能都将得到前所未有的飞跃, 这将是一个划时代的问题.

难解问题与易解问题之相似性

1）最短 vs.最长简单路径
单源最短路径问题：对有向图G，时间O(VE)，P问题
两点间最长路径：NPC问题，即使所有边上权为1
2）欧拉环 vs.哈密尔顿圈（G为无向图或有向图）
欧拉环：G中有通过每条边恰好一次的环？P问题，多项式时间可解
哈氏圈：G中有通过每个顶恰好1次的圈？NPC问题

NP完全问题的求解

减少搜索量
简单算法是穷举搜索，时间为指数, 于是可以采用以下算法减少搜索量

• 分枝限界法
• 隐枚举法
• 动态规划

可以提高效率，但时间复杂度不变

优化问题
降低优化要求，求近似解，以得到一个多项式时间的算法。即：找寻在容许的时间内得到容许精度的近似最优解的算法, 于是引出近似算法的研究