1. 更好资源首页
  2. 爱思想

施卫江:P/NP难题的系统论破解

  

   【摘要】 解决NP问题的关键,运用什么方法去判断存在着NP型可转化P型的算法?该文指出:需要辩证系统论。转化是NP自身的结构与功能之间“自否定”的过程,是矛盾互动、互缠的二元性辩证过程,而服膺于“同一性”规律形式的数学则难以处理自否定转化。辩证系统论是演化的法则、动态的过程,把NP型转化成P型看作是自组织演化的突现,而突现的可能性依耗散结构原理有四项条件:开放性、非平衡、非线性、涨落。以“旅行商问题”为例子来分析判断这四项条件,得出结论为全不符合。其原因在于该问题所给出的条件是一维数据,实质即一元性,无法快速有效演化而突现。该文用哲学思辩取代数学演算是全新的方法。

  

   【关键词】  NP问题; 旅行商问题; 辩证法; 系统论; 二元论; 突现

  

A solution of systems theory to the P/NP problem

SHI Wei-jiang

(Freelance Writer, New York City, NY, USA)

  

   [Abstract] The key to solve the NP problem is how to judge the existence of an algorithm for a conversion from some NP to P? For this purpose, dialectical systems theory is introduced for transformations which processes “self-denial” from its structure and function conversely and interactively of some kind of NP, a dualistic contradiction indeed. Mathematics is subject to the “identity” rule and difficult to tackle self-denial transformations. Further, mathematics, being of incompleteness,isn’t helpful to solve the NP problem. Dialectics is an evolutionary theory, a dynamic process, demanding connection all aspects of things, so a systematic approach is adopted. Regarding the transformation from NP to P as an emergence of self-organization evolution, four requirements for dissipative structure can be proposed for the judging possibility of emergence of evolution: opening, non-equilibrium, non-linearity, fluctuation. Taken the “Travelling Salesman Problem” as a typical example of NPC , it be concluded that none of the four requirements could be met. The reason is that the condition given by TSP is one-dimensional data only, which is the essence of Monism that couldn’t boost evolution and emergence quickly and efficiently.

  

   [Keywords] NP problem; Travelling Salesman Problem(TSP); dialectics; systems theory; dualism; emergence

  

   【正文】

  

   被美国克雷(Clay)数学研究所宣布列为七个千僖年数学难题之首的“NP=P?”问题,难倒了当今众多的数学家。因该问题极具重要性,今天的计算机科学领域遇到的不少重要难题都与此有关,为此博得了无数学者的关注和思索。笔者尝试用系统科学的思想去思索,寻觅灵感,独辟蹊径,或可有所收益。

  

1.辩证思维的引入

   欲解“NP=P?”,一个最基础的立场是,如何看待符号“=”?我认为应看作为辩证逻辑的转化符号“施卫江:P/NP难题的系统论破解”,若是,则问题可陈述为:NP型可否自我演化(转化)为P型?符号表达:NPP? 若设为可能性的存在,则追问:什么条件下可以演化?

  

   为什么应是“施卫江:P/NP难题的系统论破解”呢?查看NP=P?的问题,符号“=”的左右两边存在着形式与内容、结构与功能上显著不对称:解法上前者是非确定性解题,时间复杂度为指数式,而后者是确定性的多项式解,这就是可计算性等级的差别,故难以使两者在质的形态未变情况下相互指认而相链接上。

  

   若使NP问题获得“施卫江:P/NP难题的系统论破解”而成立,须突破NP型自身在形式和内容上的限制而进行自我否定,进行时空大转换,生成为后者,如此作转换NP内部又非得调用自身结构的资源,而用于自身作转换的功能(能量),结构与功能两者相互转换,互为主客,于是必然要上演一场自反性的矛盾进程。

  

   我们知道,凡是“=”的规律都得服从于同一性原则。尽管形式逻辑、数理逻辑和数学是分属不同的学科,但都具有类似的本质:研究人的认识的知性阶段的思维规律,其规律都要求保持思维形式和思维内容的同一性,即让思维的对象保持确定性,从而使思维对象获得质的肯定性。亦即使得“质”在规定不变的情况下,对“质”进行同态性表述,故所反映的只是事物的量变关系,即在不发生质变前提下所发生的一切量的积累过程,实质为形而上学的“一元论”。

  

   且以形式逻辑为例,在黑格尔看来就是知性思维,在《小逻辑》里论述道:“在知性逻辑这里,思维被认为是一种单纯主观的和形式的活动”[1]。也就是说,知性思维没有客体性质的内容,此类推理只适用在主客体关系不变的谓词演算场景,没有实践的品格,因此不需要“自否定”转换,单纯地寻求形式的自恰性、相容性,如此必使得一阶的形式化体系不完备性(哥德尔《不完备性定理》)。

  

   图灵机的可计算性理论表明:命题的条件与求解必须符合一价逻辑。在价值形态上看,任何计算机的功能运作都是对计算题进行形式化后还原成“一阶逻辑”运算,归入客体的属性,在处理高度非线性的复杂性事物上,形式逻辑、数理逻辑,数学,即使配上高速计算机都显得衣襟捉肘、难以应付。唯有人才能够高扬主体能动性,赖以“对象化”生存,与动物完全生存于具体和现实中不同的是,“人则把一个有力的‘否’投向这种现实”[2],有能力去创新,填补现有条件下的不完备性。这样的思维就上升到辩证法的“相互作用”的矛盾范畴:“同一矛盾原则是构成其他一切自然现象的基本原则,由于有了内在矛盾,同时自然被迫超出其自身。”[3]

  

   在一阶逻辑形式中,数学就是形式化公理确定之下的数字游戏。数学的游戏规则若用形式逻辑的语言表达就是:矛盾律 A ≠ ┓A( A不等于非A) 、同一律 A = A ( A 等于A ) 、排中律:A V ┓A(A不能同时既等于A又不等于A)。在这三条规则下,对事物的分析与演绎本质上就是形式逻辑的方法。

  

   但是思维的一阶形式却无法完整(完备性)反映自身的矛盾运动,对此黑格尔论述道:“同一矛盾原则是构成其他一切自然现象的基本原则,由于有了内在矛盾,同时自然被迫超出其自身。”[4]这就需要我们运用辩证法所专注的“运动、变化和发展”以及其能够描述事物自我矛盾转化的思维来解决。辩证思维是一个高价的非线性过程,这被黑格尔描述为“相互作用”的矛盾范畴,是高级的运动形式,能够越出一价形式所不完备性的框架,来思索复杂性问题。

  

   复杂性问题专家埃德加·莫兰(Edgar Morin)对于辩证思维有着深刻的领悟:“一个严格的决定论的宇宙是一个只有有序性的宇宙,在那里没有变化,没有革新,没有创造。而一个只有无序性的宇宙将不能形成任何组织,因此将不能保持新生事物,从而也不适于进化和发展。一个绝对被决定的世界和一个绝对随机的世界都是片面的和残缺的,前者不能进化而后者甚至不能产生。”[5] 在许多学者看来,莫兰把“复杂性理解为是与辩证法的同一”[6]。这里提到了复杂性的要害:至少要由二元(确定性与非确定性两者同时进行)、乃至多元来建构。单纯的“决定论”就是一元论,而单纯的“无序性”也同样是一元论,凡是一元构造都不能有效推动辩证法的演化。NP问题就是如此,其之所以如此复杂而难以判定,到底可否转化为P型?就在于它是准二元构造的非严格的非确定性:寻找算法极为困难,验证却极为容易;多项式难解,指数式必解。真正的复杂性总是存在于有序性与无序性的交界之处,即在称之为“混沌”的地方,这样的“混沌”样式恰构成了典型的对称性破缺的命题,所谓“非对称创造了世界”,举凡创造性的非对称论题均需要二维以上元素来参与构造,对于二元及以上的演化的事物需要辩证思维才行之有效。

  

对混沌理论做出贡献的美国科学家肖(Robert Shaw)在《奇怪吸引子、混沌行为和信息流》一文中指出,“混沌是宏观标度与微观标度的桥梁,(点击此处阅读下一页)

它能使信息由小世界传到大世界,能量由大世界传到小世界,它既是能量的渠道,又是信息的通道。”[7]在这里,系统的宏观熵增与微观熵减两极相通,处于统一体中,蕴含着对称破缺的命题。譬如在耗散结构中,混沌恰是吸引子,是信息之源,它使能量、信息和熵更富有生机和活力。当然,但若单纯的“混沌”仅是以“质料因”为主体的底层基质,只是一种自然而然的状态,就显得不足以快速有力推进演化,若否此则另需要形式因的推动。对此,美国物理学家福德(Joseph Ford)说道,“演化就是混沌加反馈”,我们可以将“反馈”看成是系统演化的自否定参与。

  

2.系统论思想的引入

   前面所陈述的就是哥德尔定理的变形:一阶形式无法完整(完备性)反映事物自身的矛盾运动,若欲区分真与假,就无法获得可证性。因而NP问题就是如此复杂性,据称“是用存在性二阶逻辑可表达的语言集合”[8],为此需要突破框框,除了辩证法,还得运用系统论方法。“自复杂性理论诞生以来,人类对世界本质的认识正悄悄地发生着变化。首先,人们逐渐认识到,普遍性、确定性、有序性、线性、可逆性、可量化等思维模式具有明显的片面性。因为事物的本质,除了上述特性外,显然还存在着偶然性、随机性、不确定性、无序性、非线性、不可逆性、不可量化等情况,以及还存在着自增强性、耗散结构、熵与负熵等情况。”[9]后一类的特征和情况恰是NP问题所特别显现出来的。总之“健全的思维形式应当是逻辑与直觉、形式与内容、理性与感性等多元思维模式协同互补,交互催化的共同体。”[10]

  

   正如许多学者指出,辩证法与系统论之间有着高度的相关性,它们仿佛就是同构的一体两面。凡是复杂性的事物,当由低级进阶至高级形态的时候,欲获得更好的认识,人们发现,必须以动态来取代静态的思维,这就是辩证法思想。如果说,辩证法是在时间之轴上展开事物的“运动、变化和发展”,那么系统论就是在空间座标中将事物的单元(维)、一阶扩充至多元(维)、高阶的复杂性升级。时空相互依存而不可分离,事物在运动、变化和发展中,必然会发生“分叉”现象,若应用单一元素和维度就不足以描述和分析其情况,于是必然需要系统论方法;同样,系统论的分析强调事物的对称性破缺,必然会产生事物的动态之感,亦即时间上的差异性,于是须适用辩证思维。互溶之中萃取两者,得到的并集可称为:“辩证系统论”或“系统辩证法”。

  

   NP是如此的复杂性问题:若按简单思路去历遍、查询而筛选,这便是一阶域内解题,为指数式非确定性解。但若突破常规,尝试找出一个便捷的算法,这需要由解题人的灵感和智慧来构思,即需要高等级价值维度的“形式因”参与,使之大力提炼NP型的“质料因”。正如弗勒德指出的,“复杂性本原于客观事物本身以及我们对于客观事物的抽象”[11],亦即由辩证法和系统论思想的主客双重结构来建立。人是灵性生命,具备创造性构思,但是也得依赖于特定时空的悟性为客体内容条件,即赖以NP问题自身的形式和内容、结构和功能的特征,去调用问题之中自身资源,从中吸取动力养料···,可见是一个互为缠绕的辩证过程,这反映了一个自组织的本质:对称性破缺演化,由此,我们该适用辩证且系统演化的思路去探索NP问题。

  

   NP问题源自于数学命题,但由于我们要采用系统论的方法探讨,以下的论述和论证就不得不舍弃大部分数学方法的精密计算,而使用“系统科学与数学的交叉”,即两者的并集。因为系统科学本是横断交叉科学,它要求所用基本的哲学概念具有极大普适性,同时又得兼顾“用数学来描述系统科学的基本概念和原理,只能采用数学中的另外一部分,即结构型的数学”[12]。

  

   邓晓芒宣称:逻辑的最高形式就是自由,辩证法精神就是人的灵性,是高等级的价值形态,无法形式化,“因为辩证法的根本精神、主体以及基本特性都是与形式化不相融的。”[13]对此我们也必须舍弃纯粹数学的方法。

  

3.解题就是系统的突现

   我们把某个NP课题与解题人一起看成是一个完整的解题系统,人是有着自我意识的自组织,因此一个完整的解题系统也就成为了自组织。我们不妨设定某位解题的人具有相当高的智慧和灵感,他也许能够领悟到某一待解的NP系统其结构和功能之微妙,找出一个比较历遍法来便捷得多的多项式算法来,如此“解题”意味着系统产生出“突现”来,亦即系统的结构和功能得以演化而升级,系统的秩序由无序转为有序、低序转为高序,突现是系统论和复杂性的中心话题。

  

   关于有序性、无序性的概念可借用埃德加·莫兰(Edgar Morin)的话,“什么是有序性?这是所有的重复性、稳定性、不变性,所有能够处于一种高度可几的关系的庇护下、被纳入对一个规律的依存的范围中的东西。什么是无序性?这是无规则性、相对于一个既定的结构的偏离、随机性、不可预见性。”[14]

  

   生命系统赖以负熵为进化动力,NP系统秩序的描述亦可借用熵的概念,负熵可用信息量来表达:I=log施卫江:P/NP难题的系统论破解=-logP,即信息量I为事件出现概率P的倒数的函数。信息量既然是负熵,那么,系统的信息量愈大,熵值愈小,系统的有序度就愈高。于是莫兰的“高度可几”就是概率P值大,P值大就是I值小,即负熵的绝对值大。

  

   我们在此所讨论NP问题,显然与人的利益需求的价值矢量密切相关,其“秩序性”高低可依据于其解题速率,即体现为主体性人的功利目的性,解题快速即为“高度可几”,反之亦然。无疑,就针对同一问题的同一规模的时间限度而言,多项式比指数式快捷得多,某NP型若经努力找出多项式之解,即进阶至P型的高有序性,反之依然。

  

4.以旅行商为例解析

   据统计,大部分的NP型要么可归为P型,要么就是NPC型。NP完全问题集又可分类为6大种类,其中归类为“排序问题”(Sorting Problems)中的“旅行商问题”(TSP),为NP中研究得最多的问题。由于TSP是NPC集,靠约化的传递性,其他的NPC问题都能约化到它,因此TSP显得尤其重要,本文仅以TSP为例来剖析NP系统之突现。当然,对TSP剖析清楚了,还不算是解决NP问题的全部,但可算是一个关键性突破。

  

   TSP定义:给定一系列城市和每对城市之间的距离,求解访问每一座城市一次并回到起始城市的最短回路。它被认为是组合优化中的一个NP困难问题,作为计算复杂性理论中的一个典型的判定性问题。TSP的另一个版本是:给定一个图和长度 L,要求回答图中是否存在比L短的回路。该问题被划分为NP完全问题。TSP的穷举算法在运气最差情况下就是全排列的历遍数:(n-1)!/2,其复杂度为:O(n!),经专家运算转化,得出该问题的时间复杂度为指数式:施卫江:P/NP难题的系统论破解

  

5.突现发生的必要条件

   解题TSP,一种傻瓜办法就是枚举法,历遍各种组合可能,则为指数式时间的非确定性解。如同主体性羸弱的低级生命,其“自然选择”进化机制就是靠随机性和漂移性,靠非确定性的尝试来谋取进化之道,因而呈现为“低有序性”方法。另一种是强主体性的“自组织”算法,自组织是指混沌系统在随机识别时形成耗散结构的过程。当有了高级智慧的参与,则需要由系统自身“构型”成势,让智慧来悟性,即从系统内部鲜明的结构特异性中产生出自身演化的进阶功能。

  

   普利高津创立的耗散结构理论认为,一个自组织的耗散结构能否成立,须看其自身是否符合四项条件:开放性、非平衡、非线性、涨落——这些似乎遥相呼应着亚里士多德的实体构造学说和发展体系的“四因说”:质料因、形式因、动力因、目的因。以下展开“四因”讨论。

  

5.1开放性

   一个成规模的NP问题之解决,需要解题人怀着解题使命来行使思维的指令,即作为“负熵”接受者和输送者的灵性生命体,他一方面吸取外界的各种有用信息,另一方面,解题人头脑中必定预设了康德主义的先天纯直观的时空形式,他肩负着解题令使先验时空形式与从待解某NP问题中的“质料因”上获得的经验实际相结合,提炼感性认识,历经数次交互反馈而酿成知性认识,使之对具体NP做出判断。由此观之,他是推动系统演化的“形式因”,能够进行价值类型的较高复杂度的思考,所以这样的自组织起码具有某种程度的开放性,然而尚有一个“度”的问题。

  

   NP解题既然是自组织过程,其开放性须由自身的特征条件来表现。那么TSP给出的条件是,仅为所有的端点之间的距离,而距离的数据纯粹是标量——这等于说:所提供的条件纯粹是一维性质的。获知了这些标量,解题人单凭直觉和知觉依然难以较快地获知这些标量的确切位置何在,尤其是当问题的规模变大时,即使通过计算,也很难快速地获知所有端点的确切位置,进而说,各个点之间的互相位置构造形式。在解题中起着“构型”角色的人,迫切需要的就是涵盖各端点和各条边的二维信息,可是TSP中,解题人所能得到的有效解题信息量,即负熵(P为解题概率)只能是一维形式:I=-log P = -log 2/(n-1)!,显然绝对值太小。

  

一个平面几何结构的完整建立需要二维数据。要解决图论问题,需要G(V,E)的二维数据集。然而TSP是一个无向强连通图,它的每一个端点都是等效的“四通八达”,端点位置纯粹一维数组建立起来,(点击此处阅读下一页)

但是建立好的点阵依然是一维形式的实质——当端点数变大时,解题人难以快速又准确地构形。通常,解几何题须要依赖于人的视觉功能构造起位置判断,以获知题中的空间形式。人们熟知,包括人在内,自然界里所有动物的视觉、听觉、嗅觉的器官全都是成双成对的,绝非单个,就是为了需要快速感知物体确切的空间位置——这就是生命的神经系统经自然选择后进化而得来的功绩。

  

   开放性是系统的结构和功能之间相互作用的表达。耗散结构的典型特征是对称性破缺,从而分叉现象。系统科学中辩证互动明显存在于:质料与形式、结构与功能、分叉与破缺、突现与分层、非线性与复杂性等等上,角色和因果常常互换而反馈,其中分叉和破缺可以成为开放性的突出标志。然而TSP给出的条件是一维数组,就多项式突现来说,分叉和破缺显然是不足够。

  

5.2非平衡

   在热力学中,平衡态是指隔热的系统其各部分宏观性质在长时间里维持稳定不变,非平衡态就是对平衡态的破坏。平衡与对称、非平衡与非对称性,两者意思较为接近,区别在于层次、侧面和适用范围。所谓对称性,是指对象的某一特征在一定变换(运动或操作)下的不变性。序与对称性是反向消长的关系,对称性越大有序性越小;反之亦然。热力学的概念当然可以作推广。

  

   系统论中,所谓“序”是有“差别的相似与相似的差别”的概念,序就是系统中出现层次的表现形式。而突现就是差异性原理,表现为序的升降变化,可用“序参量”来量化表达,而在描述系统差异性原理方面的,有“层级理论”。

  

   NP的解题实质是问题系统从无序走向有序的过程。普利高津称:“非平衡是有序之源”,系统要走向有序,就必须打破平衡,使对称性发生破缺,有序就是对称性破缺后突现发生的结果。非平衡态就是系统状态呈现层级差异性,这不仅表现在对称破缺前与后之间的状态差异上,而且也表现在破缺之后的结构与功能之间的差异性增加上。唯有差异显然的可分辨性存在于系统结构之中,成为系统层级功能上的有序性之源,才会使得系统打破平衡态,较快地实施突现。

  

   非平衡要达成耗散结构,必须要激发“非平衡相变”,使得结构自身产生分支,也就是系统“分叉”现象。这在突变论中称之为:“分层”。非平衡是否足够达到远离平衡态,使之产生新的有序结构来,要看系统能否越过相变的阈值点。

  

   系统中功能与结构常常互动互换的,“分层是突现现象得以显现的场所和条件,落脚依然在层级。因此,‘层级’是一切层级理论的核心,它一方面是一种展布在空间中的尺度序列,另一方面它也是一种依次排列于时间中的控制序列。”[15]

  

   进而,“复杂自然现象是在层级中被组织起来的,其中每一个层次都是由若干个整合系统建构起来的。”“自然界之所以在层级中被组织起来,那是因为对于任何系统,甚至是中度复杂的系统,层级结构提供了最可行的形式。”[16]

  

   我们来看TSP的情景,它处在偏离平衡点不远的近平衡态:已知条件所提供的仅是一维形式的数据组,即没有明显的二维分层。由于结构层次简单,系统就单一层内数据间的“弱势位差”去催化突现,尚不足以越过相变的阈值点,若欲快速取得突现,只能纯由随机而定。

  

5.3非线性

  

   事物凡构成线性型或非线性型的,经过线性变换(空间反演)后,可转为对称或非对称的形态,因此线性或非线性型在系统自组织中所发挥的功能,就是对称或非对称的具体化,非线性型可使系统突显的实质恰是对称性破缺

  

   反多来,对称性之所以会破缺,发生突现效应,其根源又是在于系统构成要素之间的非线性相互作用,越过临界域值而催化系统的状态突变、分叉效应(多重选择)和相干效应(长程关联)。对此,普利高津论述道:“对于耗散结构所必须的另一个基本特征是在系统的各个元素之间的相互作用中存在着一种非线性机制。”[17]

  

   代数理论中,一个数学函数L(x)为线性的,可以是指:

  

   定义1:L(x)是个只拥有一个变数的一阶多项式函数,即是可以表示L(x)=kx+b的形式(其中k,b为常数)。

  

   定义2:L(x)具有以下两个性质:

  

   可加性:L(x+t)=L(x)+L(t)

  

   一次齐次性: L(mx)=mL(x)

  

   我们以n个端点的TSP图为例,若唯有一个路径是最短的。假如我们采取穷举法解题,第一次查询得到成功的概率:

  

   P(1) =1/[(n-1)!/2]= 2/(n-1)!

  

   若此次查询验证为不符,则进行第二次查询,其查对概率为:

  

   P(2)=2/[(n-1)!-1],

  

   ······

  

   当第K次查询时,其猜对的概率为:

  

   P(k) =2/[(n-1)!-(K-1)]=2/[(n-1)!-K+1],

  

   当(n-1)!>>k时,则

  

   P(k-1)≈P(k)≈P(k+1)

  

   这表明,在时间尺度的初期阶段查询上,每一次猜对的概率相当接近,此阶段TSP系统路径元素的猜对率上呈现为高度的线性相关,也因此,猜对的概率极小,即很难以获得系统的突现。

  

   再由一次齐次性公式:L(mx)=mL(x)},代入得:P(mk)≈m·2/[(n-1)!-K+1],

  

   如果(n-1)!>>k,k为试猜(查询)序数,m为试猜总数,m ≤ k。

  

   可见,TSP在试猜(查询)的总数m与猜对的概率关系上,在初期阶段来看,两者也是近似的线性关系。近线性关系就表明了此时候的系统处在近平衡区

  

   倘若持续不断进行指数式穷举,则积少成多,从量变到质变,从近平衡区渐渐离开而缓慢进入非平衡区,找到答案的概率逐渐递增,系统缓慢趋向突现之势。

  

   因为随着 k数值渐渐趋向于(n-1)!,P(k)渐渐趋近于1,于是TSP系统渐渐由近似线性向非线性产生质变,系统发生突现的概率渐渐趋大。由于(n-1)!为指数式表达,这时候k数值也就达到了指数式的规模。

  

   TSP的线性特征还在于,无论挑选哪些条路径进行查询,都是等值的猜中率,因而具有高度对称性的。因为TSP是无向强连通图,其每一个端点都可通向任何其他的端点,因此就端点而言,其个性差异仅在于边距的各不相同,然而这恰是一维的形式。

  

   然而,在空间的组合上,TSP毕竟是一复杂系统的结构,不具有加和性。如果我们设想,将图TSP的n个端点集Vn(n∈Vn)拆分成二组子集:

  

   Vm和Vo,n=m+o。

  

   即:Vn=Vm∪Vo,Vm施卫江:P/NP难题的系统论破解Vn,Vo施卫江:P/NP难题的系统论破解Vn,Vm∩Vo=Φ。

  

   分别将这二个子集组成二个新的TSP子图予以独立解题,那么,设n顶端TSP解题的最大历遍数为:

  

   T(n) =(n-1)! /2

  

   而二个小的子集TSP解题历遍数分别为T(m)和T(o):

  

   T(m)=(m-1)!/2 ; T(o)=(o-1)!/2

  

   显然, T(n)=T(m+o)> T(m)+ T(o)

  

   这表明,在空间结构形式上一个TSP系统是不能在分立要素中进行解析,也就是呈现强非线性关系,因此若对TSP进行空间结构分析恰为解题之道。

  

   然而现实的问题表现在,空间结构的形式上,TSP所提供的只是一维的数组,即仅为一个变数,尽管提供了强连通图的所有边距,但是只要进入实际规划运算,总是存在“短程纠缠”(short-range entanglement),这是说,复杂性系统各要素总是首先从它最邻近的要素那里获得信息,并对这个信息做出反应,在较短时间内(即多项式表达)复杂性系统的各要素之间几乎都是在短程上相互作用。至于说起长程的影响,则需要考虑的情景复杂得多,视域空间须要极大地扩展,这就需要指数式来完成之。因此,无论是人脑,抑或电脑去操作应用的解题,只要问题规模很大的话,都是只能在近距离上起步,逐步且逐级地去思索解题方案,譬如:启发法、回溯法、贪心算法、分支限界法、遗传法、退火法、等等。

  

统观全图的结构形式,只管短程而不管远程,对于颇具规模的问题就难以找到最佳方案,“短程作用”解题是一种近似的方法。所以,TSP提供的边距筛选的实际操作是近似线性关系。(点击此处阅读下一页)

  

5.4涨落

   所谓涨落,是指对系统稳定状态(通常维持在:平衡态、对称性、线性区、时间不变性的定态)的偏离。耗散结构理论认为,事物的演化需要由“对称性破缺”来推进,涨落为系统的对称破缺提供可能,这就是“生序原理”——“通过涨落来达到有序”的原理。[18]

  

   涨落并不必然导致系统的相变、有序、演化,即不是充分条件,系统还需对其要素的涨落作出反应并进行相关选择。这是因为系统的结构有其层次性特点,不同层次其功能是各不一样,各级层次的波动是否构成要素的涨落还有待于甄别和判断。

  

   通常涨落耗散定律是发生在称为临界阈值点的附近,在表征涨落相关的空间距离上,以标度(scaling)来呈现——由涨落达成耗散,其根子在于不同要素之间相互起作用,这就要求系统必须出现“巨涨落”,促使系统突破阈值,远离平衡态。

  

   因此,突现问题的关键须从标度上看要素作用,若判定为“巨涨落”,则引起快速突现,否则系统只会作出微弱反应,滞留原有层次依旧,或以小概率而突现。

  

   TSP是一个不稳定系统,它的稳定状态唯有在未解之时。凡是试猜查询都可看作是一次随机猜对的“涨落”,都是对于原有稳定状态的瓦解。即如从n(n-1)/2条边中任意选取n条,经过非线性映射后,试猜就可以看成:该系统n个元素进行的“粒子热运动”,根据热力学相对涨落定律,其涨落度为:施卫江:P/NP难题的系统论破解。可见,当n趋向于较大值时为微涨落,此即所谓“大数定律的破缺”,这就是说,复杂性系统的演化,往往具有“对初始条件的敏感依赖性”,不遵守严格的决定论。

  

   涨落现象引起的根源在于不同要素,而唯有差异性显著者才真正构成不同要素,形成作用力显著的层级“势位差”,方使得相互作用显著起来,激起巨涨落。

  

   然而TSP为无向强连通图,它的所有端点全是无差别的全连通,端点间的距离即个性差异,仅由一维数组来提供,如此靠一维来激发的涨落,前面已经论述过了,是在同一层级内的不充分开放、近平衡态、近线性区里的短程空间进行的,近似于n个变量的一次方函数关系,即近似线性型。试图将该问题的许许多多次查询(微涨落)依次累加起来,可以构成为一个猜对概率递增的算术级数系列,这系列当然是对TSP系统的稳定态进行算术级数的偏离,然而这一系列“偏离值”的累加在运气糟糕时则为耗费指数式时间,因而在多项式内难以确认有巨涨落。若使对系统“稳定态”的偏离值加大,欲达成几何级数(即非线性)的程度,以促使巨涨落,则须系统的结构成为几何问题形式的二维表达,然而TSP给出条件却莫能。

  

6.“中国邮路问题”为什么归为P类?

   中国邮路问题(Chinese postman problem, CPP)是,一个邮递员送邮件,从邮局出发要走完他负责投递的全部街道(所有街道都是双向通行的且每条街道可以经过不止一次),完成任务后返回邮局。他应按怎样的路线走,使得所走路程最短?

  

   这是一个图历遍的问题,在一个连通的无向图中寻找一最短的闭合路径,且此路径需通过所有边至少一次。解法如下:

  

   若待解图中恰有欧拉回路,因为欧拉回路通过所有的边,则任何一个欧拉回路即为此问题的解。

  

施卫江:P/NP难题的系统论破解

   图1  用图来模拟一个镇的街道,标示红色的路口有奇数条路通过。

  

   施卫江:P/NP难题的系统论破解

   图2 所有奇数边端点组成的K4完全图。

  

   施卫江:P/NP难题的系统论破解

   图3 最后的解,红色部份是新增的边及其对应的长度。

  

   若图中不存在欧拉回路,则其中必存在有奇数个边的端点,且这类的端点一定不少于2个。因此有些边需要再重覆一次,使奇数边的端点变为偶数边的端点。

  

   【图1】假设有一个镇有14条路及9个路口(路口分别编号为 1,2, …,9),其路和路口对应的图(边上的数字是各边的长度值)中有4个端点(编号 1, 3, 6 及9)有奇数个边通过,因此这个图不存在欧拉迴路。后续要作的在图中使几个边重覆,使图中所有的端点均有偶数边通过。例如若图中 {1,3} 及 {6.9} 边重复,所有的端点均有偶数边通过。不过增加的长度不一定最少。

  

   为了要确定重复哪个边可以使原图的端点都有偶数边通过,且增加长度最少。先画出所有奇数边的端点的完全图 K4【图2】,边上的数字是从一端点到另一端点(可以经过其他完全图 K4中省略的点)的最短长度。若选择边 {1,6} 及 {3,9},所有端点都经过一次,而总长度4+2=6最短。

  

   【图3】因此原来的图中,连接端点 1 和 6, 端点 3 和 9 的边再重覆一次,所有端点均有偶数个边通过(右边第 3 图)。因此任一个欧拉路径即为此问题的解答,如以下的端点顺序 (1,2,3,4,9,3,1,8,7,3,9,7,6,9,5,6,7,8,1) 即为一解。图中红色的部份即为重覆的边。[19]

  

   由此,中国邮路问题被确认为一个P型。我们注意到,这个问题所提供的已知条件,是一个完整的平面图——充分的二维数组:G(V,E),它的每个端点之间都是有差别的,即与临近端点的通路数各不相同,且容易辨认,如此则使解题者快速在视觉上完成“构型”,解题只需三个多项式步骤即可找到所求路径。

  

   参考文献:

   [1][德]黑格尔:《小逻辑·§192·附释》[M] 贺麟译, 上海人民出版社,2009年版。

   [2]舍勒:《人在宇宙中的地位》,贵州人民出版社,1989年版,第40页。

   [3][德]黑格尔:《小逻辑·§80》[M] 贺麟译, 上海人民出版社,2009年版。

   [4]黑格尔:《小逻辑·§80》

   [5]埃德加·莫兰:《复杂思想:自觉的科学》[M],北京大学出版社,2001年版,第159页。

   [6]黄欣荣:《复杂性科学与哲学》[M],中央编译出版社,2007年版,第11-13页。

   [7]转引自:武杰、李润珍:《对称破缺的系统学诠释》,原载《系统科学学报》2008年1期。

   [8]《维基百科》和《百度百科》中均有相关的陈述。

   [9]向成军:《浅论复杂性与思维方式革命》[J],原载《中国校外教育(下旬)》 2019年3期。

   [10]马晓苗:《哥德尔定理证明对自指悖论的化解及其自组织涌现机理》[J],原载《系统科学学报》2020年1期。

   [11]许国志主编:《系统科学与工程研究》[M],上海科技教育出版社,2000年版,第598页。

   [12]苏淼:《关于广谱哲学的交叉性学科特点》[J] , 原载《华北水利水电大学学报(社会科学版)》, 2016 年4期。

   [13]葛宇宁:《辩证法形式化的批判性思考》[J],原载《唐山学院学报》,2016年4期。

   [14][法]埃德加·莫兰:《复杂性思想导论》[M],华东师范大学出版社,2008年版,第95页。

   [15]黄欣荣:《复杂性科学与哲学》[M],中央编译出版社,2007年版,第11-13页。

   [16]转引自:武杰、李润珍:《对称破缺的系统学诠释》[J],原载《系统科学学报》2008年1期。Simon H.A. The Organization of Complex Systems [C]//Howard Patter, ed. Hierarchy Theory. Braziller, New York :1973:205.

   [17][比]普里高津:《从混沌到有序》[M],曾庆宏等译,上海译文出版社,1987年版,第25页。

   [18]武杰、李润珍:《对称破缺的系统学诠释》[J],原载《系统科学学报》2008年1期。

   [19]关于“中国邮路问题”的材料摘录自【维基百科】,经过了笔者编辑。

  

转载文章,作者:更好,如有侵权,请联系删除。链接:https://makebetter.best/archives/6265

发表评论

电子邮件地址不会被公开。 必填项已用*标注

联系我们

400-800-8888

在线咨询:点击这里给我发消息

邮件:[email protected]

工作时间:周一至周五,9:30-18:30,节假日休息