設置

第六百七十七章P≠NP?

  手中的論文放下,徐川靜靜的看著首頁上的標題,回味著整個閱讀過程。

  對于他這類人來說,看到一篇新領域的好論文,完全不亞于普通人吃到一道從未享用過的山珍海味,足夠回味一生。

  而大正整數因子的多項式分解問題,毫無疑問符合這份標準。

  事實上,大數的因數分解問題是數學中最基本、最古老,而至今仍受人們重視但未能完全解決的問題之一。

  它在數論領域的重要性和難度都完全不弱于在偏微分方程領域的楊米爾斯方程存在性。

  因為大整數可能是素數也可能是合數,所以解決這一問題的前提在于先對給出的大數進行判斷,判定給定的數是否為素數(即素性判定難題)和將大合數分解為素因數的大數分解兩方面。

  在數學中,它與質性檢測難題很相似,但質性檢測已被完全證明多項式時間可解,而大數因子分解問題仍然懸而未決。

  甚至,幾百年來,大數因子分解問題既未被證明是多項式時間可解的P問題,也未被證明是NP完備問題。

  不過在眼前的這份論文中,徐川看到了一份詳細的答案,亦或者說,一條通向數論終極問題之一的道路。

  仔細的回味了一下手中的論文,徐川睜開眼,從書桌的角落中拖過來電腦,點開了威信聊天框。

  “論文我已經看過一遍了,非常的優秀!”

  手指輕盈的敲擊著鍵盤,一句夸獎隔著電腦屏幕傳遞到了上千公里之外。

  這并非違心,而是他發自肺腑的感慨。

  雖然很早之前就知她在數學和計算機上的天賦都很強,但他卻也從未想過有一天她能進入這一個領域。

  在學術界,亦或者說在網上,人們在討論一門學科的時候,如果它某些方面具有較高的研究價值和實用性,本身足夠難學的同時,在就業市場上存在一定的難度,就會被人稱為“天坑專業”。

  而這些專業通常被認為是基礎學科,學習難度大,就業前景和薪酬待遇往往不如其他專業。

  比如最常見的‘生化環材’四大天坑。

  不過很多時候,位于自然科學中最基礎的數學專業卻基本不會被人記入,亦或者很少有人說它是天坑專業。

  并不是它不夠難,而是它太難。

  如果說其他的專業是一個天坑,你可以看得到坑底有很多人(學者)在艱難的往上爬。

  那數學專業就是一座懸崖,下面深不見底,云霧繚繞,扔個東西都沒有回音那種。你看不到它到底有多深,也看不清楚里面有多少人,只能看到寥寥可數的大牛在貼近懸崖頂部的云霧之上飛來飛去.

  用數學界的話來說,這些飛在云霧之上的大牛,都是數學界的神仙。

  徐川自己就是飛的最高的那個。

  而如今,在解決了大正整數因子分解具備多項式算法難題后,劉嘉欣也一躍從數學的深淵飛上了云霧之巔。

  盡管這并不是完整的解決了PNP?這道千禧年難題,只是其中的一份階段性成果,但它的難度,以及對全世界的影響力,卻是極大。

  因為,它除了是數學和計算理論中的一個重要問題之外,任何一種證明都將對數學、密碼學、算法研究、人工智能、博弈論、多媒體處理、乃至哲學、經濟學等等許多其他領域產生深遠的影響。

  換個可以說涉及到所有人的領域:“密碼!”

  在如今,無論是手機,或電腦,亦或者郵件等等需要進行信息交流,或者涉及到賬號安全的東西,都涉及到密碼的存在。

  而在計算機密碼學中,目前來看,最重要的公開密鑰算法是RSA。

  它是計算機通信安全的基石,確保加密數據無法被解。RSA加密是非對稱加密,可以在不直接傳遞密鑰的情況下,完成解密。

  簡單的來說,它是由一對密鑰來進行加解密的過程,分別稱為公鑰和私鑰。

  假設:甲方和乙方相互通信。乙方生成公鑰和私鑰。甲方獲取公鑰并對信息進行加密(公鑰是公開的,任何人都可以獲取)。甲方使用公鑰對信息進行加密。

  只有私鑰才能被破解,所以只要私鑰不泄露,信息的安全性就可以得到保證。

  所以它廣泛應用在各領域,其安全性決定于對大整數分解的難度。

  當合數所有的因子都很大時,采用強力方式得到具體的因子是很困難的,而這也正是RSA體制理論的核心。

  但在解決了大正整數因子分解具備多項式算法難題后,RSA加密系統的算法可以在找到方法后,快速的坍塌成一個‘解’。

  這意味著什么,自然不言而喻。

  當然,這只是理論上的,實際上要做到視RSA等加密算法如無物,即便是有了這篇論文,目前也不可能做到。

  或許等未來量子計算機成熟后,再配合這份論文,那大概就是真正的橫行于傳統計算機領域了。

  至于現在,只能說還需要等待時間的發酵。

  不過可想而知,這篇論文將對整個世界造成多大的影響。光是計算機通訊密碼,就將迎來一次徹底的大轉變。

  那些建立在傳統大正整數因子分解上的加密方式,恐怕會被各國拋棄和更換。

  畢竟,它在理論上已經不再安全了。

  深夜,書房中,威信的咔嗒聲輕輕的響起,在發了一句信息后,徐川撥通了視頻通話。

  等待了一會后,視頻被連接上,對面,同在書房中的劉嘉欣出現在手機中,露出了修長天鵝頸和淡白色睡衣。

  看著視頻對面的學姐,徐川的目光自然而然的落在了那露出的一抹比睡衣更白的肌膚上,一時間竟愣了一下,忘了說話。

  雖說因為公司和數學上的事情兩人經常打交道,但兩人見面的時候基本都是在白天,哪有這種看對方穿著睡衣的時候。

  對面,劉嘉欣注意到到了徐川的目光,這才反應過來自己在家里穿著睡衣的狀態,抿著嘴有些不好意思的整理了一下上衣的扣子。

  “咳”

  徐川回過神來,輕咳了一下開口道:“論文我已經詳細看了一遍,目前來說,它非常的優秀!雖然我無法肯定的說你已經完全解決了這個問題,畢竟它還沒有經過同行評審,但要我給出看法,毫無疑問,你做到了。”

  “謝謝。”視頻通話對面,劉嘉欣展顏微笑著說道:“麻煩你了,這么晚了都還在讓你幫忙。”

  “不不不,千萬別這么說!”

  聽到這話,徐川迅速搖頭道:“這并不是麻煩,如果真是,那我希望這樣麻煩能多來一些!”

  對于一名數學家來說,能看到這樣的一篇論文,別說是還沒睡,哪怕是睡著了被人喊起來也不會有任何的意見,沒能在第一時間看到,才會覺得是可惜。

  當然,對于一名女生來說,或許這并不是一個標準的答案。

  不過很顯然,這會兩人的注意力倒也都沒在學術之外的事情上,兩人的思路都集中在手中的那篇論文中。

  “.對二次篩因子分解法做深入變化,引入哈密頓圖判定方法和多項式函數算法,這樣可以對復零點的存在問題進行轉換,將其化為線性方程組求解問題,再從給出了判定方程組f10,···,fk0存在復數解算法的復雜性。”

  “.根據費馬小定理,如果p是素數,則a(p1)≡1(modp)對所有的a∈[1,n1]成立。所以如果在[1]中隨機取出一個,發現不滿足費馬小定理,則證明n必為合數。”

  視頻通話中,劉嘉欣解釋著大正整數因子分解具備多項式算法難題的解決核心和思路,徐川則隔著屏幕時不時的提出一些自己的問題。

  雖說論文已經完整的描述了大正整數因子分解具備多項式算法難題的證明過程,但獨自看論文和對照著論文聽創造者的解釋,是兩個完全不同的概念。

  如果看論文就能弄懂所有的問題,那數學界也不會要求在這些世界級猜想解決后證明者開報告會了。

  時間在深夜中滴答滴答的流逝著,直到過了零點,兩人才停下了下來。

  書房中,徐川眼神明亮中帶著一些思索,沉思了片刻后從走神中回過來,看向了視頻通話對面的劉嘉欣,笑著道:

  “很出色的證明,將二次篩因子分解法升華,引入哈密頓圖判定方法和多項式函數算法的同時扭轉坍縮大整數,這已經可以說是一項新的數學工具了。在前人的基礎上,你做的比我想象中還要優秀出色。”

  對面,劉嘉欣抿著嘴輕輕搖了搖頭,道:“可是我找不到一項能將NP類問題轉化成P類問題的方法,也無法解決NP類問題和NPC問題。”

  看著對面的學姐,徐川笑了笑,調侃道:“想著一次性解決PNP?猜想?,你這也太貪心了。”

  微微頓了頓,他接著道:“在PNP?問題中,大正整數因子的多項式分解問題本身就是最難的兩大問題之一了。能解決這個,剩下的問題距離伱或許也并不是很遙遠。”

  對面,劉嘉欣想了想,猶豫了一下還是開口道:“但是我覺得這個問題還能遙遠,或許它永遠無解。”

  聞言,徐川停了一下,有些訝異的挑了挑眉,問道:“你覺得P≠NP?”

  雖然他并沒有長時間和全神貫注的研究過這個難題,但七大千禧年難題中所剩不多的猜想,他自然也有過探索。

  盡管并不是很深入,但老實說,他對于這個問題的看法卻并非PNP,而是P≠NP。

  即那把能夠解開這個世界上所有問題的簡單鑰匙并不存在。

  這算是他冥冥中的數學直覺了。

  即便是在今天晚上看完了大正整數因子的多項式分解問題的證明,PNP往前推進了一大步,他依舊保留自己的看法,覺得P≠NP。

  當然,徐川也從來都不認為在一個沒有解決的問題上,自己的看法就一定是對的。

  畢竟他也只是一個人,只是學習過的知識比普通人多一點點而已,并不是全知全能的神。

  但在PNP?難題上,或者說在P類問題和大正整數因子的多項式分解問題上,眼前這位學姐應該是目前走的最遠的人之一,或者說就是走的最遠的。

  如果她都覺得PNP?猜想或許是不正確的,再結合數學界大部分人的看法以及他自己的直覺,或許PNP并不存在。

  即NP類問題也永遠不可能‘全部’都坍縮成P類問題。

  或許有人或奇怪既然大正整數因子的多項式分解問題都已經被證實了,那為什么P反而不等于NP了?不應該是會朝著PNP更推進一步嗎?

  對于這個問題,只能說PNP?猜想本身就并不是一個完全定義的數學難題。

  它在克雷數學研究所的七大千禧年難題中,全程叫做‘NondeterministicPolynomial的問題,即多項式復雜程度的非確定性問題。’

  PNP?猜想中,兩邊的P和NP并不固定,它針對的是無窮無盡的多項式和非確定性問題。這種情況下,要想證明P≠NP并非易事。

  如果是PNP,你需要保證每一個NP類問題都能坍縮簡約成成P類問題,如果P≠NP,那你則需要證明每一個潛在的算法都必將失敗。

  而這里的算法和問題,并不僅僅指現在,還包括過去和未來的所有所有。

  所以與其說PNP?問題是一個數學猜想,倒不如說它是一種思考的方法,一種根據問題的內在難度對其進行分類和認識的方法。

  對面,劉嘉欣點了點頭,輕聲道:“嗯,或許這個難題無解,我們既不能證明PNP,也無法證明P≠NP。”

  “我嘗試過去解決的一個NP完全問題,但卻發現不可能找到一個在所有情況下都能解決該問題的算法,只能盡所能地爭取最好的結果。”

  徐川點了點頭,笑著道:“看樣子我們達成了共識。”

  笑了笑,他往后靠在椅背上,接著道:“如果單論問題來說,不僅僅是PNP?難題,有很多難題都一樣,往往我們都無法直接的去解決它。但很多時候,研究它們的過程才是最為精髓的東西。”

  “比如現在,大正整數因子的多項式分解問題就賦予了我們一種通用的框架和工具,有助于思考如何應對從實際需求中產生的那些困難的問題,也能幫助我們更好的去完善數學與其他科學的發展。”

  “而這些,才是最重要的!”

  (本章完)

大熊貓文學    大國院士