|
|
请举出下面比较形象或好理解的例子
1、有解但无算法
2、无解也无算法
3、可计算与不可计算
4、可证明与不可证明
5、详细讲讲集合、群、族
关于NP问题和NPC问题，我以前已经发过帖子了，我的文档中也有该文章。
我将该文转贴如下：
什么叫做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问题，所以都是难解的问题。
下面依次回答你的5个问题：
1。有解但无算法的问题：
比如圆周率Pi的小数点后面是否有连续的100万个0。因为Pi是一个客观存在的实数，所以Pi的值是确定的，因此这个问题的解也是存在的。要么是yes,要么是no，虽然我们不知道他到底是什么，但他是客观存在的，不随时间改变，不随人的认识而改变。但是没有算法可以计算这个问题的答案。当然，可以用一种苯办法来解决这个问题，就是不停地计算Pi的小数点后面的值，如果发现了有连续的100万个0，则这个问题的答案就是yes，但是如果没有发现，我们必须一直计算下去，而且永远无法停止~~，所以这种苯办法根本称不上是算法，因为他不满足算法在有限步内终止的条件。所以这个问题是没有算法的（至少目前认为如此，也许以后可以从数论中找到某种方法来求出小数点后面是否有连续的k个0，或从概率的角度计算Pi的小数点后面的值的分布等等等等）。
2.无解也无算法的问题：
例如，给定任意一个命题，是否存在一种算法判断这个命题是真是假？这就是著名的图灵停机问题。如果存在这个算法，那么我们只要找到这个算法就可以一劳永逸了，以后无论拿到什么新的命题，都可以用这个算法来验证一下，立刻就知道该命题是真是假，这样我们就掌握了整个宇宙的终极真理：）。但是图灵已经证明了这样的算法是不存在的，这个问题也是无解的。（证明中主要利用了康托尔对角线删除法，就是用来证明实数和自然数不等势的那种对角线删除法）
3。可计算与不可计算：
根据图灵-丘奇论题，：
1。可计算的问题就是能被图灵机计算的问题；（图灵的定义）
2。可计算的问题就是使用lamda演算系统可以计算的问题；(丘奇的定义)
图灵丘奇论题与其说是定理，不如说是算法的定义。因为算法本身就是一个不精确的概念，到底什么是算法，以前一直没有确切的定义。而图灵-丘奇论题则从数学上给出了算法的形式定义。
图灵说：所有的图灵机能计算的问题都是有算法的（也就是可计算的），所有有算法的问题都可以用图灵机计算。这个论题本身是无法证明的，它就像物理中的光速不变定律一样，是一条自然定律，不能加以逻辑上的证明，只能用实验来检验。而目前来看，图灵命题也和光速不变一样，经得住历史和时间的检验，现在即使发展到了量子计算机，还是没有摆脱图灵机的约束，量子计算机上可计算的问题也是普通的图灵机上可计算的问题，只不过计算效率不同而已。
不可计算的问题的两个例子前面已经说过了，一个是Pi的例子，另一个是图灵停机问题。
4。可证明性与不可证明性
在一个公里系统中，有若干条公里，有一些推导规则，在系统中进行定理的证明，就是从公理出发，利用这些规则推导出新的定理。如果最终能得到我们需要证明的命题，则该命题为真；如果最终得到了和我们需要证明的命题相违背的命题，则我们要证明的命题为假。
如果把系统中所有的定理看作图中的节点，假如从定理i1,i2,..ik根据系统的规则可以推导出定理j，则从i1,i2,...ik分别连接一条到j的有向边。这样整个公理系统构造成了一个有向图。定理的证明过程事实上是在公理系统中从公理表示的节点出发，构造一颗到达目标命题节点的“证明树”。因而定理的证明就和图论中的路经搜索类似（BTW，这就是定理自动化证明的基本原理）。
超级天才歌德尔在25岁的时候提出了著名的歌德尔不完备性定理。该定理指出：在任何一个公理化系统中，要么存在着矛盾，这个系统是不完备的。
所谓存在着矛盾，就是可以证明命题A成立，也可以证明命题A的否命题成立，这就自相矛盾了。
所谓不完备，是指系统中存在着一些命题，无法证明它成立，也无法证明它不成立。这就好像在一个图中存在着某些孤立点，从基本的公理节点出发永远无法访问到这些孤立点。
歌德尔在“不完备性定理”的证明过程中构造出了一个无法证明是真是伪的定理。具体说起来比较麻烦，我根据自己的理解将其简化为下述的简单形式：
命题A = “命题A不成立”
现在问命题A是否成立。如果命题A成立，则根据命题A的内容，命题A应该不成立；如果命题A不成立，则根据命题A的内容，命题A又应该成立。
这个例子很不严谨，因为它事实上混淆了语法和语义层次。但我觉得这个例子可以作为歌德尔的例子的一个简化版本。歌德的那个例子要比这个严谨和复杂得多，但实质上是差不多的，也是利用了逻辑中的悖论。
罗素等人所提倡的解决这种悖论的方法就是给谓词逻辑分层次，从而产生了一阶谓词逻辑、二阶谓词逻辑等。像上面的例子，罗素认为命题A的内容描述了命题A本身的性质，这就超出了命题A所能表达的范围，他认为这样的A不是合法的命题。
5。自己看离散数学书吧~~
10 楼66766（毁人不倦）回复于 2002-04-17 19:50:50 得分 0
事实上，我刚看了皇帝新脑、并行程序设计、知识发现、数学危机
非但没有看懂，而且完全动摇了我对计算的看法
我一致认为世界是确定的，但不可计算
但正是皇帝新脑对计算的否定
是我又产生了可计算的想法
否则程序员岂不都成白痴了
当然程序员的认识永远没有数学家和物理学家深刻
我个人认为，在给定条件下
必定存在算法
这种算法的精确度
应该可以满足需要
1、pi和根号2有区别吗
2、谢谢指点
3、pi值除了割圆
还有很多代数式计算
其不可计算
好像并不是因为没有算法
而是np问题，请指点
4、似乎歌德尔的非数学描述本身也有逻辑问题
我现在对反证法表示怀疑了
逻辑到底几元
公理是否有共同的唯一起点
还是多个公理共容
如果是由某一公理推倒不出另一公理
那么歌德尔定理就不会成立
5、我没看过离散数学
以后再看吧，上面的几本书已经把我搞糊涂了
问一下大家程序员应该走那么远吗
可是其中有一部分确实是我编程需要的
6、世界到底是确定的还是随机的
7、计算到底是连续的还是离散的
明天结帖，还是务实点好Top
11 楼starfish（海星）回复于 2002-04-18 00:45:06 得分 15
首先，从目前的科学发展来看，这个世界应该是不确定的。否则的话就会陷入科学决定论的怪圈。
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年前的人的区别？仅仅是为了满足人类的好奇心，也有必要了解一下最新的科学知识。
程序员有很多种，有的就像盖房子的民工一样，只会砌砖头，就算他再熟练，经验再丰富，也只能砌砖头；有的就像包工头一样，可以搞管理；有的就像建筑设计师一样，可以做设计；还有的就是那些科学家了，他们研究物理、研究材料、研究如何才能盖出更好的房子，他们的研究不是针对如何建造某幢具体的大楼，而是影响全人类的建筑水平。究竟做那种人，取决于你自己的定位。 |
|
IP卡
狗仔卡
发表于 2008-12-8 16:12:12
提升卡
置顶卡
沉默卡
喧嚣卡
变色卡
显身卡
楼主