施衛江:P/NP難題的系統論破解

選擇字號:   本文共閱讀 303 次 更新時間: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.fetgub.tw),欄目:天益筆會 > 科學精神 > 科學專欄
本文鏈接:http://www.fetgub.tw/data/122791.html
文章來源:作者授權愛思想發布,轉載請注明出處(http://www.fetgub.tw)。

1 推薦

在方框中輸入電子郵件地址,多個郵件之間用半角逗號(,)分隔。

愛思想(aisixiang.com)網站為公益純學術網站,旨在推動學術繁榮、塑造社會精神。
凡本網首發及經作者授權但非首發的所有作品,版權歸作者本人所有。網絡轉載請注明作者、出處并保持完整,紙媒轉載請經本網或作者本人書面授權。
凡本網注明“來源:XXX(非愛思想網)”的作品,均轉載自其它媒體,轉載目的在于分享信息、助推思想傳播,并不代表本網贊同其觀點和對其真實性負責。若作者或版權人不愿被使用,請來函指出,本網即予改正。
Powered by aisixiang.com Copyright © 2020 by aisixiang.com All Rights Reserved 愛思想 京ICP備12007865號 京公網安備11010602120014號.
工業和信息化部備案管理系統
广东快乐10分平台