舟山新闻网,为您提供最佳全面的最新舟山新闻信息!
当前位置:主页 > 科技 > 正文

最新证明面临质疑丰台火车站最新消息:P/NP问题为什么这么难?(3)

时间:2017-08-16 12:52 来源:http://www.bmeetg.com/ 作者:舟山新闻网 阅读:

  “Peter Shor(另一位TOC成员)发现大整数分解的多项式量子算法时,量子计算界确实炸了。”在《麻省理工学院新闻》的报道中,Sipser介绍说。“Peter的突破引发了计算机和物理两个领域的一大波研究。事实上,Shor的发现一度点燃了人们利用微观尺度下反直觉的量子力学来在多项式时间内解决NP完全问题的希望。但现在看来这似乎不太可能:大整数分解问题实际上是几个不知道是否为NP完全的NP困难(NP-hard)问题。”同样地,人们不能证明不存在多项式的大整数分解算法,所以尽管人们相信量子计算对于大整数分解这样的问题会带来计算能力的提升,但这点同样尚未得到证明——更别提对于一般问题的指数级别的突破了。

Perter Shor

Perter Shor

  对此,Scott Aaronson介绍了Grover算法作为例子。Grover算法对于输入规模为N的无序数据库给出的~2^{N/2}时间复杂度的量子搜索算法。但早在Grover的算法之前,Bennett等人已经证明~2^{N/2}是最优解了!换句话说,任何在2^N那么大的大海中捞一根针的量子算法都需要至少~2^{N/2}步。相应地,经典计算机需要~2^N步。所以至少可以说,对于“一般的”或者“无结构的”搜索问题,量子计算机对于经典计算机来说只能给出某种加速——事实上是平方加速——但不会是像Shor算法那样的指数加速。

  为什么这个加速会是平方的,而非立方或者其他什么的?Scott Aaronson尝试着给出了答案,且尽量不牵扯到Grover算法或者Bennett等人最优化证明的具体细节。他认为,从根本上讲,我们得到平方加速的原因是,量子力学是基于2-范数而非1-范数的。经典来讲,如果有N个解,其中只有一个是正确的,那么查询一次后我们距离得到正确答案便有了1/N的概率,查询两次后便有了2/N的概率,查询三次3/N,依此类推。因此,我们需要~N次查询来获得足够大(即接近1)的概率猜出正确答案。但是如果用量子力学,我们是对一组几率幅态矢进行线性变换,它是概率的平方根。所以我们这样考虑这个问题:查询一次后我们有1/\sqrt{N}的几率幅得到正确答案,查询两次后是2/\sqrt{N}几率幅,查询三次后是3/\sqrt{N}几率幅,依此类推。所以经过T次查询后,我们得到正确答案的几率幅为T/\sqrt{N},然后概率便是|T/\sqrt{N}|^2= T^2/N。因此我们需要大约T ~\sqrt{N}次查询来得到接近于一的概率。

  量子计算机概念的引入给我们带来了新的复杂度类,其中最典型的一个便是BQP,即有界错误量子多项式时间类(bounded-error quantum polynomial time)。与BPP类似地,BQP指可以在多项式时间内用量子计算机以小于1/3的错误概率解决的问题的集合。很多人认为,BQP是量子物理学控制的宇宙中计算机可以切实解决的所有问题组成的类。

  BQP包含BPP与P,且包含于PSPACE,但它与NP的关系就没那么确定了。于是,新的关系图如下:

BQP加入后的复杂度类关系示意图

BQP加入后的复杂度类关系示意图

  综上所述,量子力学的加入一定程度上为P/NP问题带来了新的曙光,但是想要解决P/NP问题还是需要走很长的路。

  4可能的解决方案?

  在通往P/NP问题的路上,有很多的尝试,例如量子力学、电路下界、交互式证明技术等,都先是让人们看到了希望,然后随着研究的深入,又让人们觉得这些可能还不够。那么,还有什么“有希望的”解决方案吗?Scott Aaronson介绍了芝加哥大学计算机系教授Ketan Mulmuley的几何复杂性理论纲领(Geometric Complexity Theory program, GCT program)。GCT试图将P/NP问题与代数几何、表示理论等很多看起来比较远的数学概念联系起来。

Ketan Mulmuley

Ketan Mulmuley

  “我觉得GCT就像计算机科学领域的弦论,”Scott Aaronson说,“一方面,它实现了如此惊人的数学联系,以至于一旦你看到它们,你就会觉得这个纲领一定会在正确的道路上。而另一方面,如果你用已经解决了多少它最初想解决的问题,而不是这一纲领本身来评价它的话,那么可能它连最初的想法都还没有实现。”也就是说,或许正是因为还没有足够深入的了解,所以GCT还保留着解决P/NP的希望。“甚至GCT纲领最疯狂的支持者也预测说得有几十年的跋涉,而且其在数学上的复杂性也吓唬到了其他每个人。”

  是的,P/NP问题就是这么难。

  感谢Scott Aaronson对本文的意见。

  主要参考文献:

  1。 MIT News对于Michael Sipser和Scott Aaronson的采访,采访部分获Scott Aaronson授权翻译:

  

  

  2。 Aaronson S。 Quantum computing since Democritus[M]。 Cambridge University Press, 2013。

  3。 Sipser M。 Introduction to the Theory of Computation[M]。 Cengage Learning, 2012。

(责任编辑:舟山民生在线)

顶一下
(0)
0%
踩一下
(0)
0%