planeheart的头脑风暴
注册日期:
2013-09-16 15:53:09
上次登录:
2016-05-11 02:38:27
邮件地址:
saintpal@163.com
兴趣领域:
数学,物理,人工生命,系统科学,计算机科学
“设想如果P等于NP……想像一下所有会用消元法的人就能成为高斯，凡能欣赏交响曲的人就都能成为莫扎特。”
——Scott Aaronson
本文简单地谈及Scott Aaronson的综述《NP-complete Problems and Physical Reality》（arXiv:quant-ph/0502072）中特别有启发性的地方。
1，关于可物理实现的计算的讨论除了能帮助理解计算以外，同时也能帮助理解物理规律本身。（也即是：认为计算是物理规律的一部分，类同CTD命题的精神）
2，只要对量子力学中算符的线性要求做些微的放宽，例如，温伯格引入的非线性算符（这些工作出现在温伯格试图研讨的所谓非线性量子力学中）得到允许，则我们可以在新型量子计算机上用多项式时间解决PSPACE完备问题（NP完备自然不在话下）。
3，量子力学的隐变量诠释，虽然实验结果对其非常的不利（局域性隐变量几乎已经被贝尔不等式判决实验彻底终结），但至今也不能将这种可能性排除（例如，玻姆的量子关联势诠释，包含非局域性的隐变量。或者所有认为实验者选择测量所用基底的操作会被预决的诠释，这使得目前所实施过的所有贝尔不等式判决实验的至少一个前提失效）。
假定满足一定要求的隐变量诠释正确，并具有可观测效应，则我们可以用多项式时间解决图同构问题（en.wikipedia.org/wiki/Graph_isomorphism），虽然，没有充分的证据表明这一结果能给予我们快速解决NP完备问题的计算能力。
4，综合考虑相对论和量子力学的效果，确切而言，黑洞热力学的效果，使得模拟计算的能力被严重限制。贝肯斯坦上限使得真正处理实数的计算机不可实现，即便是在没有热噪声的假想环境里也不例外。这阻断了一种通过模拟计算在多项式时间内解决NP完备问题的可能性。
5，允许闭合类时回线（通俗而言，读作“时光机”）并假定宇宙自洽性原理（允许向过去传送信息，然而宇宙的机制自动会保证因果律不被打破，当然你也无法杀死你爷爷）能让我们通过所谓“时间循环逻辑”（某种意义上说，让时空本身实现了自指）用多项式时间（以图灵机实际运行的固有时为准）解决PSPACE完备问题，并且这点对经典计算和量子计算具有同等效力。
6，热力学第二定律与NP完备问题的难解性可能存在相当的联系（然而这里并没有什么关键的证明）。
7，我的评论：
有趣的地方在于，2中的非线性量子力学会允许我们超光速通信（量子不可克隆/删除定理要求严格的线性性，去除这个限制，意味着我们可以用备份方式任意恢复测量前的量子态，从而可以设计在不用经典信道的前提下实现量子通信的方案），根据相对论我们知道，超光速通信意味着存在类空间隔的事件间可以存在因果关系，这马上就遇到了5中的因果时序的问题。而5和2得到的结果都是计算能力强化到能在多项式时间内解决PSPACE完备问题，我想这不是巧合。
2014-05-28 09:39:51
对热力学第二定律和NP完备问题很感兴趣呀，他说什么了？
2014-06-05 16:38:33
几乎没什么内容。
不过结合Bennett的Logical Depth and Physical Complexity和Zurek的那两篇论文大致可以猜出思路。
考虑一只内存有限的麦克斯韦妖，如Zurek的论证，妖精不可能使气体的熵无限降低，因为充分长的时间后妖精将被迫开始删除测量记录。然而，如果妖精以比较有效的方式来删除记录，i.e，删除记录的压缩版本（其长度不小于原记录的科尔莫格洛夫复杂度）。那么妖精可以在一定的时间内保持气体的熵总量少于原值，对于某个只关心气体的热力学熵的观察者来说，妖精等于是“打破了”热力学第二定律。
然而这有一个前提，就是Zurek的工作中假定妖精完成这个记录压缩的过程所用的时间总是可以忽略。然而记录压缩所需要的时间复杂度可能是很高的，虽然这不提供一个实时时长，但是执行一步计算操作的最小用时是确实存在的物理限制。如果这个记录压缩需要的时间过长，远长于测量记录将内存填满的时间，则上面提及的妖精的行为是不可实现的。
关于时间复杂度因素的参与依然是个难解的问题。
2014-06-05 16:46:25
所以，实际上妖精为了要有效地“打破”热力学第二定律，必须要在将测量记录做最大限度的压缩和避免压缩的时间复杂度过高之间取得一定的权衡，而非一味尽力压缩测量记录以换取最大差值。
登录后才可以评论，马上登录。