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

选择字号:   本文共阅读 303 次 更新时间:2020-09-07 13:39:27

进入专题:   NP问题   旅行商问题   辩证法  

施卫江  
它能使信息由小世界传到大世界,能量由大世界传到小世界,它既是能量的渠道,又是信息的通道。”[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=-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!),经专家运算转化,得出该问题的时间复杂度为指数式:

  

5.突现发生的必要条件


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

  

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

  

5.1开放性


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

  

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

  

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

    进入专题:   NP问题   旅行商问题   辩证法  

本文责编:limei
发信站:爱思想(http://www.aisixiang.com),栏目:天益笔会 > 科学精神 > 科学专栏
本文链接:http://www.aisixiang.com/data/122791.html
文章来源:作者授权爱思想发布,转载请注明出处(http://www.aisixiang.com)。

1 推荐

在方框中输入电子邮件地址,多个邮件之间用半角逗号(,)分隔。

爱思想(aisixiang.com)网站为公益纯学术网站,旨在推动学术繁荣、塑造社会精神。
凡本网首发及经作者授权但非首发的所有作品,版权归作者本人所有。网络转载请注明作者、出处并保持完整,纸媒转载请经本网或作者本人书面授权。
凡本网注明“来源:XXX(非爱思想网)”的作品,均转载自其它媒体,转载目的在于分享信息、助推思想传播,并不代表本网赞同其观点和对其真实性负责。若作者或版权人不愿被使用,请来函指出,本网即予改正。
Powered by aisixiang.com Copyright © 2020 by aisixiang.com All Rights Reserved 爱思想 京ICP备12007865号 京公网安备11010602120014号.
工业和信息化部备案管理系统