NP难问题

NP难问题 首先，从目前的科学发展来看，这个世界应该是不确定的。否则的话就会陷入科学决定论的怪圈。 20世纪以前的物理学认为自然界存在两种物质:一种是粒子，它的运动状态和运动规律可以用牛顿力学来描述;另一种物质是场，它的运动规律遵循Maxwell方程组。但无论是哪一种，他们的运动方程都由Laplace方程决定。给出系统的初始状态，通过求解运动方程，就可以唯一地确定系统在任意时刻的运动状态。按照经典物理的理论，整个世界是确定的，世界上没有真正的随机。所谓的随机只是因为我们对所需的参数认识不够而造成的。以掷硬币为例，我们如果知道了硬币的一切参数(包括质量、密度等)和外界的一切参数(包括重力，抛掷角度，抛掷力大小等)，那么掷硬币的结果是完全可以通过运动方程计算出来的。将这种思想推而广之，我们的宇宙在诞生之初所有的粒子和场的初始状态都是确定的，如果宇宙的运动发展存在着规律，那么整个宇宙的发展过程在宇宙诞生之初就被完全确定了。宇宙中的任何事物，太阳系、地球、人类、甚至人类的思维等等，一切的运动变化结果，都在宇宙诞生之初就完全确定了。 1819年，拉普拉斯出版了《关于概率的哲学论文》[Essai philosophique sur lesprobabilites]。拉普拉斯写道:“我们应当把宇宙的现状看作它的先前状况的结果，看作随后状况的原因。假定一位神明能够知晓使得自然生机勃勃的所有的力，和构成自然的所有物体在一瞬间的状况:对于这个神明来说，没有任何事物会是不确定的;未来会和过去一样在它眼前出现。”在1927年前大多数物理学家都同意上述见解。这种拉普拉斯决定论断言，如果给出宇宙在某个瞬间的状况、情境，宇宙在无论未来还是过去的任何瞬间的状况就是完全被决定的。这种观点在西方哲学界被称为“科学决定论”。 然而，量子理论的诞生彻底打破了这种确定性～量子理论断言:我们的宇宙中存在着根本意义上的随机，这种随机不是因为参数不够无法计算造成的，而是因为时间、空间和物质之间一种未知的纠缠关系产生的。按照量子理论，人的主观意识甚至会对外界的客观实在产生影响～这就完全违背了经典的唯物主义(事实上经典的唯物主义应该进行修正，但我们的教科上还是100年前的东西)。对于量子而言，如果人不去观测它，它处于不确定的状态;而一旦观测它，它就 会陷入一个确定的状态。量子所处的状态和人的观测方式有关。从这个意义上来说，人的主观决定(选择的观测方式)将会直接影响到客观世界的量子的状态～ 其次，Pi和根号2都是无理数，但是Pi要更特殊一点，它是一个普适常量，它的物理意义显然要比根号2大得多。你恐怕曲解了NP问题的含义，NP问题通常是指没有多项式时间算法的问题，更精确地说，NP问题是指可在多项式时间内验证的问题。从这个定义上说简单的排序问题也是NP问题，因为它可在多项式时间内验证。但我们通常所说的NP问题都是指难解问题(尚未找到多项式时间算法)。Pi的那个例子和这个不同，并不是计算的复杂度太大，而是算法无法终止～哈密尔顿回路问题是NP完全问题，它还没有找到多项式时间的算法，但他是有算法的，而且这个算法可以在有限时间内终止。就算该算法的复杂度是指数级的，对于一个确定的输入这个算法可能需要算到宇宙毁灭，但它总是能终止的。而对Pi的计算，是永远无法终止的，因为它是无限不循环小数～你要搞清楚的是NP问题和不可计算问题是两回事，我们讨论一个问题可不可以计算，并不关心计算该问题的复杂度是多少，而是关心原则上是否存在能够在有限时间内终止的机械算法。而对Pi而言，没有这种算法。 反证法本身确实存在问题。直觉主义者一直都怀疑反证法，甚至抵制反证法。他们认为形式逻辑中的公理 ~(~A) => A 并不成立。因为A的否不成立，没有理由说明A一定成立。换句话说，他们认为排中律不成立。当然，这种争论未必有结论，究竟信仰那种学派完全是个人自由。事实上这些不同的学派的理论只是在基本概念和基本体系上有差异，最终得到的高层次的定理并不相互矛盾。因为高层次的定理很容易被实践检验，如果和实践相抵触的公理话，那种学派早就不存在了。 公理系统是人为规定的。事实上可以有很多不同的公理系统，比如数理逻辑中，欧洲、中国与苏联、美国这三地的学者都喜欢用不同的公理系统。不同的公理系统最终得到的高层次的定理并不会相互矛盾，这些公理系统之间可以相互推导出对方的公理，所以他们是完全等价的。使用何种公理系统也完全是个人的喜 好，当然了，最好使用那种和人类直观相符合的公理系统。你也可以用和人类直观相违背的公理系统，照样能得到一些系列和实践并不矛盾的结果。著名的例子就是非欧几何的诞生，它就是违背了人类的直观，但是却开创了新的数学领域。 同一个公理系统的各条公理之间是不可能相互推导的，当然更不可能相互矛盾。可以由公理推导出来的命题叫做定理，所谓系统的公理就是不能由系统内其他公理推导，但是却显然正确的命题(如果不正确该系统就会有矛盾)。 逻辑究竟怎么划分目前似乎也无定论。 最后，计算显然是离散的。原来人类以为世界是连续的，量子理论告诉我们世界也是离散的，这个世界上没有真正的连续，都是一种离散的近似(就好像整个世界是Matrix中的计算机模拟出来的一样^o^ )。例如，在本世纪初，按照经典物理的电磁辐射理论，人们无法解释黑体辐射能量密度按照频率分布的实验结果。于是Plank提出光是以离散的形式辐射出来，每一份辐射是一个光量子，它的能量为ε=hv，其中v是辐射频率，h是Plank常数。Einstein通过光电效应则意识到:电磁辐射不仅发射和吸收是以量子形式进行的，而且传播也是以量子形式进行的，Einstein认为辐射场本身就是由光量子组成，每个光子的能量就是ε=hv。所以能量具有最小的单位，能量是离散的。现在普遍认为整个世界都是离散化的。 离散数学一定要好好学习，这是计算机科学的基础。 程序员到底要走多远，没有一定的。事实上不懂相对论，不懂量子理论并不妨碍你成为优秀的程序员。但是我认为作为一个21世纪的现代人，这些常识性的科学知识还是应该了解的，否则怎么能体现出我们和100年前的人的区别,仅仅是为了满足人类的好奇心，也有必要了解一下最新的科学知识。 程序员有很多种，有的就像盖房子的民工一样，只会砌砖头，就算他再熟练，经验再丰富，也只能砌砖头;有的就像包工头一样，可以搞管理;有的就像建筑设计师一样，可以做设计;还有的就是那些科学家了，他们研究物理、研究材料、研究如何才能盖出更好的房子，他们的研究不是针对如何建造某幢具体的大楼，而是影响全人类的建筑水平。究竟做那种人，取决于你自己的定位。 什么叫做NP问题，什么叫做NPC问题? 首先说明一下问题的复杂性和算法的复杂性的区别，下面只考虑时间复杂性。算法的复杂性是指解决问题的一个具体的算法的执行时间，这是算法的性质;问题的复杂性是指这个问题本身的复杂程度，是问题的性质。比如对于排序问题，如果我们只能通过元素间的相互比较来确定元素间的相互位置，而没有其他的附加可用信息，则排序问题的复杂性是O(nlgn)，但是排序算法有很多，冒泡法是O(n^2)，快速排序平均情况下是O(nlgn)等等，排序问题的复杂性是指在所有的解决该问题的算法中最好算法的复杂性。问题的复杂性不可能通过枚举各种可能算法来得到，一般都是预先估计一个值，然后从理论上证明。 为了研究问题的复杂性，我们必须将问题抽象，为了简化问题，我们只考虑一类简单的问题，判定性问题，即提出一个问题，只需要回答yes或者no的问题。任何一般的最优化问题都可以转化为一系列判定性问题，比如求图中从A到B的最短路径，可以转化成:从A到B是否有长度为1的路径,从A到B是否有长度为2的路径,。。。从A到B是否有长度为k的路径,如果问到了k的时候回答了yes，则停止发问，我们可以说从A到B的最短路径就是k。 如果一个判定性问题的复杂度是该问题的一个实例的规模n的多项式函数，则我们说这种可以在多项式时间内解决的判定性问题属于P类问题。P类问题就是所有复杂度为多项式时间的问题的集合。 然而有些问题很难找到多项式时间的算法(或许根本不存在)，比如找出无向图中的哈米尔顿回路问题，但是我们发现如果给了我们该问题的一个，我们可以在多项式时间内判断这个答案是否正确。比如说对于哈米尔顿回路问题，给一个任意的回路，我们很容易判断他是否是哈米尔顿回路(只要看是不是所有的顶点都在回路中就可以了)。这种可以在多项式时间内验证一个解是否 正确的问题称为NP问题。显然，所有的P类问题都是属于NP问题的，但是现在的问题是，P是否等于NP?这个问题至今还未解决。注意，NP问题不一定都是难解的问题，比如简单的数组排序问题是P类问题，但是P属于NP，所以也是NP问题，你能说他很难解么, 刚才说了，现在还不知道是否有P=NP或者P<>NP，但是后来人们发现还有一系列的特殊NP问题，这类问题的特殊性质使得很多人相信P<>NP，只不过现在还无法证明。这类特殊的NP问题就是NP完全问题(NPC问题，C代表complete)。NPC问题存在着一个令人惊讶的性质，即如果一个NPC问题存在多项式时间的算法，则所有的NP问题都可以在多项式时间内求解，即P=NP成立～～这是因为，每一个NPC问题可以在多项式时间内转化成任何一个NP问题。比如前面说的哈米尔顿回路问题就是一个NPC问题。NPC问题的历史并不久，cook在1971年找到了第一个NPC问题，此后人们又陆续发现很多NPC问题，现在可能已经有3000多个了。所以，我们一般认为NPC问题是难解的问题，因为他不太可能存在一个多项式时间的算法(如果存在则所有的NP问题都存在多项式时间算法，这太不可思议了，但是也不是不可能)。 类似哈米尔顿回路/路径问题，货郎担问题，集团问题，最小边覆盖问题(注意和路径覆盖的区别)，等等很多问题都是NPC问题，所以都是难解的问题。