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

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

进入专题:   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?”,一个最基础的立场是,如何看待符号“=”?我认为应看作为辩证逻辑的转化符号“”,若是,则问题可陈述为:NP型可否自我演化(转化)为P型?符号表达:NPP? 若设为可能性的存在,则追问:什么条件下可以演化?

  

   为什么应是“”呢?查看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)在《奇怪吸引子、混沌行为和信息流》一文中指出,“混沌是宏观标度与微观标度的桥梁,(点击此处阅读下一页)

    进入专题:   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号.
工业和信息化部备案管理系统