计算理论初探（3）_pvsnp

选题：关于PvsNP问题的探究

一.四类问题的定义及其区别

1.P问题

  P问题是指能够使用确定性图灵机在多项式时间内解决的所有决策问题；

如果一个公式语言L是一个P类型，那么当且仅当存在这样的一个确定图灵机M时成立：

对于所有的输入，M都会在多项式时间内运行
对于L中所有的x, M的输出都是1
对于不在L中的所有x，M输出都是0
1
2
3
4
5

2.NP问题

  NP是一组决策问题，对于这些问题实例来说，如果答案为“是”，那么表示该实例使用确定图灵机可在多项式时间内验证成功；
  进一步说，我们可以将NP问题视为由两个阶段组成的，第一阶段包括对解决方案的猜测，该阶段以非确定性方式生成；第二阶段包括确定性算法，验证猜测是否可以解决问题。也就是说，NP= Nondeterministic + Polynomial

3.NP-complete问题

  在计算复杂度理论中，满足以下情况的问题是NPC问题：
    1）该问题是NP问题；
    2）任意NP问题可以在多项式时间内规约为这个问题。
   NP

4.NP-hard问题

  在计算复杂性理论中，NP-hard是“至少与NP中最难的问题一样难”，满足NPC问题的第二个条件（即任意NP问题可以在多项式时间内规约成该问题)。它的范围比NPC问题的范围广，但不一定是NP问题。如：子集和问题就是NPH问题的一个简单的例子。

二.上述四类问题的关系

1.四类问题的韦恩图

2.关于上图所示关系的讨论

1）如果一个问题是P类问题，那么它必定也是NP问题

证明：
若A是P类问题，则它可以多项式时间内求解；
1）现在我们任意给定一个猜测解b;
2)在多项式时间内解出A的真实解a;
3)以O(1)时间比较a和b是否相等；
如此，就在多项式时间内验证了b是否是正确的解，也就满足NP问题的条件.
即：任意一个P问题都是NP问题。
Q.E.D.
1
2
3
4
5
6
7
8

2）定理：如果找到了NPC问题的多项式时间解，则所有NP问题都有多项式时间解，即：P=NP;

证明: 
任意给定一个NP问题X，NPC问题A；
1）根据NPC性质,X可在多项式时间内转化为A；
2）假设找到一个算法能在多项式时间内解决A；
3）由基本代数知识，求解X所花费的时间也是多项式级别的； 
4）由X的任意性，得出每个NP问题都有多项式解，则每个NP都是P ,则P=NP. 
5）Q.E.D.
1
2
3
4
5
6
7

  值得思考的是，NP-complete问题的概念是如何被人们提出来的？
  从规约的定义中可知，A问题规约为B问题，时间复杂度增加了，问题的应用范围也增大了。通过对某些问题的不断规约，我们能够不断寻找复杂度更高，但应用范围更广的算法来代替复杂度虽然低，但应用范围很窄小的一类问题的算法。回想前面讲的P和NP问题，联想起规约的传递性，自然地，我们会想问，如果不断地规约上去，不断找到能“通吃”若干小NP问题的一个稍复杂的大NP问题，那么最后是否能找到一个时间复杂度最高，并且能“通吃”所有的 NP问题的这样一个超级NP问题？答案是肯定的。也就是说，存在这样一个NP问题，所有的NP问题都可以约化成它。换句话说，只要解决了这个问题，那么所有的NP问题都解决了。这一类问题就是NPC 问题，也就是NP-完全问题。而这段文字也更直观地解释了上述证明方法。NPC问题的出现使整个NP问题的研究得到了飞跃式的发展。我们有理由相信，NPC问题是最复杂的问题。

3）NPC问题的存在性

如何证明一个问题是NPC问题？

1)对于问题A，证明A是NP问题；
2)证明A可以规约为问题B，其中B是一个已知的NPC问题；
1
2

上述证明方法有一个值得深思的地方，第一个NPC问题是怎么来的？

  显然，如果找不到第一个NPC问题，那么“NPC问题”这一概念的提出，对PvsNP难题的解决在实际上并没有太大的帮助。所幸，人们发现逻辑电路问题正是这样一个优美的NPC问题。
  逻辑电路问题属于NPC问题。这是有严格证明的：它显然属于NP问题，并且可以直接证明所有的NP问题都可以约化到它（NP问题有无穷多个，但这不会给证明造成不可逾越的困难）。证明过程相当复杂，我目前并不能领会到证明过程的精髓，只能看懂其大概意思是说任意一个NP问题的输入和输出都可以转换成逻辑电路的输入和输出（想想计算机内部也不过是一些 0和1的运算），因此对于一个NP问题来说，问题转化为了求出满足结果为True的一个输入（即一个可行解）。

4）如果P=NP被成功证明为真

a)最直观的就是前文中的韦恩图的变化：

在P!=NP和P=NP两种情况下，前文的韦恩图将被进一步表示为如下形式：

b) 对各大领域的影响：

对运筹学的影响

  如果P=NP被证明，那运筹学中的很多难题都将被轻松解决。比如说整数规划问题、旅行商问题等等，整个运筹学会被提升到一个难以想象的高度。点菜之类的生活小事也将得到简化，因为，点菜的选择优化问题是一个NP完全问题。运筹学的主要研究方向可能会转向NP难问题。

对密码学的影响

  密码学将是受到最大冲击的领域了。现代密码学，尤其是各种加密算法，核心都是归结到NP!=P上的。如果我们找到了多项式时间算法，密码的破解时间会被大大减少。例如常见的RSA算法，不可逆的地方在于两个大质数相乘的结果，如果只知道结果而不知道那两个素数，想把这两个素数找出来是非常难的，属于NP问题。 如果该问题被解决，RSA算法将不再可用，很长一段时间内密码学将不再安全，我们需要采取的加密方案必须将改为NP问题以外的问题，转而在量子计算机相关的量子加密算法等领域寻找新的方案。

对数学的影响

  如果P=NP被证明的话，现在做理论研究的数学家可能很大一部分要失业了。引用NPC理论奠基人史提芬·古克的一段话：“P=NP会将数学转变为让计算机对任何问题寻找拥有合理长度的证明的学科，因为我们能够在多项式时间内验证一个证明正确与否。这些问题也包括千禧年问题中的其他几个。” 因此，当寻找反例和验证反例变得同样简单，所有错误的猜想都能够被迅速推翻。同时，寻找一个数学证明和验证一个证明的正确性也变得同样简单，因此一切正确的命题也能够瞬间找到一个最简的证明。因此，理论数学家的工作会发生巨大的转变：他们不再需要考虑如何去证明一个猜想或一个定理，提出猜想就是他们的主要工作。

对医学的影响

  如果P=NP被证明的话，对医学领域也将有重大影响。生物蛋白质的折叠问题是也是NPC问题：
  自从20世纪60年代，Anfinsen基于还原变性的牛胰RNase在不需其他任何物质帮助下，仅通过去除变性剂和还原剂就使其恢复天然结构的实验结果，提出了“多肽链的氨基酸序列包含了形成其热力学上稳定的天然构象所必需的全部信息”的“自组装学说”。而原氨基酸序列的一维信息如何转变为蛋白质三维信息的，这就是问题的关键。
  如果该问题被解决，那么通过解析蛋白质折叠，就能够在治疗癌症等绝症的领域做出重大突破。

三.结束语

  综上，概括P,NP,NPC的关系以及研究现状如下：
    1.P是NP;
    2.NPC是NP;
    3.NP=P?答案不明
    4.NPC和P是否有交集? 答案不明;但可知：
      如果有,则有 P=NP >NPC
      如果没有交集，则P=NP不成立；
  若P=NP得到证明，也就是说，当我们提出一个问题的验证方法时，我们就获得了它的解法，能不能解决问题就变成了能不能提出问题，据此，统筹学、密码学、医学等领域，和我们的日常生活将受到极大的影响。