★置頂zzllrr小樂公眾號，追蹤《小樂數(shù)學(xué)科普》系列報道！

部分?jǐn)?shù)學(xué)問題可借助計算機(jī)輕松求解，還有一些問題或許根本無解。復(fù)雜性理論便是用來界定問題難度的理論體系，而數(shù)學(xué)界最知名的未解難題之一，便是P是否等于NP這一命題：倘若一道問題的答案易于核驗，那么這道問題本身是否也容易求解？

本次格雷沙姆講座先介紹艾倫?圖靈（Alan Turing）及該領(lǐng)域其他先驅(qū)學(xué)者的相關(guān)研究，再為大家梳理該領(lǐng)域近期取得的各類研究進(jìn)展。演講者是一位專攻群論與計算代數(shù)領(lǐng)域的英國數(shù)學(xué)家，科爾瓦?瑪麗?羅尼-杜加爾（Colva Mary Roney-Dougal），她是圣安德魯斯大學(xué)純數(shù)學(xué)教授，大英帝國官佐勛章獲得者，愛丁堡皇家學(xué)會會士。

作者：科爾瓦?瑪麗?羅尼-杜加爾（Colva Mary Roney-Dougal，圣安德魯斯大學(xué)純數(shù)學(xué)教授）2026-5-11

譯者：zzllrr小樂（數(shù)學(xué)科普公眾號）2026-5-17

求喜歡

演講人簡介

科爾瓦?瑪麗?羅尼-杜加爾（Colva Mary Roney-Dougal）大英帝國官佐勛章獲得者，是一位專攻群論與計算代數(shù)領(lǐng)域的英國數(shù)學(xué)家。她現(xiàn)任圣安德魯斯大學(xué)純數(shù)學(xué)教授，也是該校首位純數(shù)學(xué)系女性系主任。

羅尼-杜加爾教授本科就讀于圣安德魯斯大學(xué)，起初她入學(xué)時主修英語與哲學(xué)專業(yè)，之后才決定投身數(shù)學(xué)研究。她于倫敦瑪麗女王大學(xué)取得博士學(xué)位，隨后先后在悉尼大學(xué)、圣安德魯斯大學(xué)計算機(jī)科學(xué)系從事博士后研究，并于2003年入職圣安德魯斯大學(xué)數(shù)學(xué)系擔(dān)任永久教職，此后便一直在該校任職。

她的研究領(lǐng)域涵蓋群論（研究對稱性的數(shù)學(xué)分支）、組合數(shù)學(xué)（計數(shù)相關(guān)的數(shù)學(xué)分支）以及計算數(shù)學(xué)；她在2013年與約翰?布雷（John Bray）博士、德里克?霍爾特（Derek Holt）教授合著的研究專著《低維典型群的極大子群》The maximal subgroups of the low-dimensional classical groups，迅速成為該領(lǐng)域的經(jīng)典參考文獻(xiàn)。

除科研工作之外，羅尼-杜加爾教授十分熱衷于向大眾科普數(shù)學(xué)知識。2024年，她因在數(shù)學(xué)與教育領(lǐng)域作出的貢獻(xiàn)被授予大英帝國官佐勛章。

主持人（薩拉?哈特）：

各位晚上好。大家好，我是薩拉?哈特，十分榮幸由我開啟今晚活動的開場環(huán)節(jié)，我曾擔(dān)任格雷沙姆學(xué)院幾何格雷沙姆講席教授。我熱愛數(shù)學(xué)，相信在座各位也同樣熱愛。今晚大家將會收獲一場精彩的講座。初次來到本校的各位朋友，本次講座是格雷沙姆學(xué)院與倫敦數(shù)學(xué)會每年聯(lián)合舉辦的學(xué)術(shù)講座，稍后我們將有請倫敦數(shù)學(xué)會的代表上臺發(fā)言。

接下來由我以格雷沙姆學(xué)院代表的身份，提醒大家相關(guān)安全事宜：會場后方設(shè)有應(yīng)急安全出口，位置就在燈光所在處。我們暫未收到火警預(yù)警，若意外響起警報，請大家有序撤離，現(xiàn)場工作人員會引導(dǎo)大家前往安全區(qū)域。另外，講座結(jié)束后我們預(yù)留了五至十分鐘的問答交流時間。

線上觀看直播的各位觀眾朋友們，大家晚上好，歡迎收看本場講座。大家可以掃描二維碼進(jìn)入斯萊多（sli.do）互動平臺在線提問。現(xiàn)場在座的各位觀眾，若想匿名提問也可掃碼操作，當(dāng)然舉手提問同樣歡迎，我們會依次傳遞麥克風(fēng)，請大家拿到話筒后再進(jìn)行發(fā)言，方便全場人員聽清問題。我的開場致辭到此結(jié)束，接下來有請倫敦數(shù)學(xué)會的瑪麗?馬林登為大家介紹今晚的主講嘉賓，有請瑪麗。

嘉賓介紹人（瑪麗?馬林登）：

謝謝薩拉。各位晚上好，我謹(jǐn)代表倫敦數(shù)學(xué)會與格雷沙姆學(xué)院，歡迎大家前來參與2026年度倫敦數(shù)學(xué)會 — 格雷沙姆學(xué)院聯(lián)合講座，本場講座主講人為科爾瓦?羅尼 - 杜加爾教授。我是瑪麗?馬林登，現(xiàn)任倫敦數(shù)學(xué)會教育委員會主席，本次學(xué)術(shù)活動由我們與格雷沙姆學(xué)院聯(lián)合籌辦，我們對此倍感欣喜。

正式講座開始前，我簡單介紹一下倫敦數(shù)學(xué)會（LMS）及其行業(yè)服務(wù)工作。

倫敦數(shù)學(xué)會始建于1865年，是英國權(quán)威數(shù)學(xué)學(xué)術(shù)團(tuán)體。學(xué)會核心宗旨是推動數(shù)學(xué)領(lǐng)域發(fā)展、傳播數(shù)學(xué)知識、推廣數(shù)學(xué)應(yīng)用，目前全球會員規(guī)模約三千名。學(xué)會始終依托會員群體與廣大科研學(xué)界，助力數(shù)學(xué)行業(yè)穩(wěn)步前行。

學(xué)會開展的工作內(nèi)容十分豐富：其一，發(fā)放科研與教育專項資助資金；其二，舉辦各類學(xué)術(shù)會議與研討交流會，為取得杰出數(shù)學(xué)研究成果的學(xué)者頒發(fā)獎項與榮譽勛章；其三，出版業(yè)內(nèi)認(rèn)可度極高的數(shù)學(xué)專業(yè)期刊與學(xué)術(shù)著作；其四，面向大眾開展科普講座，探討數(shù)學(xué)教育與數(shù)學(xué)科研領(lǐng)域的各類行業(yè)議題。若大家想要深入了解學(xué)會詳情與日常工作，講座結(jié)束后可以前來與我交流溝通。

接下來為大家預(yù)告兩場學(xué)會近期舉辦的學(xué)術(shù)活動。繼本場講座之后，我們將舉辦2026年度倫敦數(shù)學(xué)會與SIAM應(yīng)用數(shù)學(xué)及工業(yè)數(shù)學(xué)聯(lián)合會聯(lián)合舉辦的戴維?克雷頓獎項頒獎暨主題講座，活動將于5月13日在倫敦英國皇家學(xué)會舉辦。該獎項旨在表彰為數(shù)學(xué)行業(yè)發(fā)展與學(xué)界建設(shè)作出突出貢獻(xiàn)的知名數(shù)學(xué)家。

牛津大學(xué)艾倫?戈里利（Alan Gorilli）會士憑借其在力學(xué)、生物學(xué)科研領(lǐng)域及材料研究領(lǐng)域產(chǎn)出的深刻且極具影響力的數(shù)學(xué)研究成果，同時長期扶持青年數(shù)學(xué)研究者、積極向大眾普及數(shù)學(xué)及數(shù)學(xué)應(yīng)用知識，榮獲2025年度該獎項，他也將在本次活動現(xiàn)場領(lǐng)取榮譽獎項。順帶一提，艾倫教授同時兼任格雷沙姆學(xué)院幾何講席教授。

下月我們還將開設(shè)數(shù)學(xué)科普傳播研討會，由兩位資深數(shù)學(xué)研究者與科普工作者本?斯帕克斯、凱蒂?斯特克爾斯主講。研討會將系統(tǒng)傳授面向大眾開展數(shù)學(xué)科普的實用思路與實操技巧，活動面向所有愛好者開放，尤其適合有志于投身數(shù)學(xué)大眾科普事業(yè)的人群。該研討會報名名額十分緊俏，有意參與的朋友建議盡早完成報名。

話不多說，接下來我隆重有請2026年度倫敦數(shù)學(xué)會 — 格雷沙姆學(xué)院聯(lián)合講座主講人登場。

科爾瓦?羅尼-杜加爾教授任職于圣安德魯斯大學(xué)，擔(dān)任純數(shù)學(xué)教授一職，同時兼任該校純數(shù)學(xué)系系主任。她本科就讀于圣安德魯斯大學(xué)，最初攻讀英語與道德哲學(xué)專業(yè)，后續(xù)轉(zhuǎn)入數(shù)學(xué)專業(yè)深耕。之后于倫敦瑪麗女王大學(xué)取得數(shù)學(xué)博士學(xué)位，博士畢業(yè)后前往澳大利亞悉尼大學(xué)開展博士后研究工作。

學(xué)成歸國重返圣安德魯斯大學(xué)后，她先擔(dān)任人工智能方向博士后研究助理，隨后正式入職該校數(shù)學(xué)系，獲得終身教職。其代表性學(xué)術(shù)著作是收錄于倫敦數(shù)學(xué)會講義叢書的《低維典型群的極大子群》，該著作一經(jīng)出版便成為領(lǐng)域內(nèi)通用權(quán)威參考文獻(xiàn)，目前引用量已超七百五十余次。2024年，她因在數(shù)學(xué)教育領(lǐng)域作出的卓越貢獻(xiàn)，獲英王授予大英帝國官佐勛章，今年又正式當(dāng)選為愛丁堡皇家學(xué)會會士。接下來讓我們以熱烈的掌聲，歡迎大英帝國官佐勛章獲得者科爾瓦?羅尼-杜加爾教授，為大家?guī)肀緢鼍手v座。

演講人：科爾瓦?瑪麗?羅尼-杜加爾（Colva Mary Roney-Dougal）

非常感謝瑪麗細(xì)致的介紹，也感謝各位觀眾在微涼的五月夜晚前來赴約，同時感謝薩拉完成開場主持。或許大家并不知曉，我和薩拉早在攻讀博士學(xué)位時期便已相識。接下來進(jìn)入今天的正式講座內(nèi)容，我先從一個貼近生活、頗具難度的實際問題說起。

大家不妨設(shè)想籌備一場大型家庭聚餐，邀約一百位親友共同赴宴，安排所有人圍坐在同一張餐桌就餐。這個想法聽起來十分溫馨，但這個大家庭里存在關(guān)系不和的親友，我們不愿讓觀念相悖、相處不合的人相鄰而坐。

為了方便講解，我暫且縮減人數(shù)，選取九位家庭成員作為示例，分別用字母代稱，其中包含愛麗絲姨媽、比爾，還有畫面下方的祖母與伊恩叔叔幾位核心人物。愛麗絲姨媽僅能與比爾、戴維相鄰就座，和其他人同坐都會產(chǎn)生矛盾；比爾性格隨和，可相鄰入座的人數(shù)有四位；我本人同樣性格開朗，也有四位可共處就餐的親友，其余人員也都有著對應(yīng)的相處限制。

大家第一眼看到這份人員相處清單，都會覺得排布就餐座位十分棘手，很難快速規(guī)劃出一套不會引發(fā)矛盾的落座方案。想要解決這個難題，我們首先需要簡化問題形式。此前我分享過該案例后，有人向我推薦過一款可統(tǒng)籌六千人大宴座次排布的專業(yè)軟件，這類軟件有著極高的市場需求，只因聚餐人數(shù)越多，座次規(guī)劃的難度就會呈指數(shù)級上升。我們可以將座次排布問題轉(zhuǎn)化為圖論模型，用簡易圖示梳理關(guān)系。

在圖示當(dāng)中，每一個圓點代表一位家庭成員，圓點之間相連的線條我們稱之為邊，只要兩人之間存在連線，就代表二人可以相鄰就餐。在專業(yè)定義里，這些圓點稱作頂點，連接線稱作邊。梳理完圖示關(guān)系后，座次規(guī)劃就等同于在這張關(guān)系圖中完成閉環(huán)遍歷，遍歷方向不受限制。

我們需要從愛麗絲姨媽的位置出發(fā)，沿著連線走完所有頂點，每位家庭成員僅經(jīng)過一次，最終再次回到起點，對應(yīng)著所有人圍桌就餐、全員落座無重復(fù)的理想狀態(tài)。

結(jié)合圖示不難發(fā)現(xiàn)這套家庭落座方案存在明顯矛盾：愛麗絲姨媽左右兩側(cè)只能安排比爾與戴維，祖母又只能坐在比爾與海蒂中間，伊恩叔叔則僅能坐在海蒂和戴維之間。按照這個限制排布六位人員后，就已經(jīng)形成閉環(huán)，剩余三位家庭成員沒有空余位置安排，也就是說依照現(xiàn)有相處條件，這場家庭聚餐注定無法實現(xiàn)全員和睦就餐。

其實想要化解這個難題并不復(fù)雜，只需緩和祖母與伊恩叔叔之間的矛盾，讓二人能夠正常相處即可。調(diào)整關(guān)系后，依舊保留愛麗絲挨著比爾、比爾挨著祖母的排布方式，再由祖母銜接伊恩叔叔，伊恩叔叔對接海蒂，順著連線依次安排剩余人員，最后由戴維回到愛麗絲姨媽身旁，就能完成全員無矛盾的落座排布，僅僅新增一條關(guān)系連線，難題便能順利解決。

這類座次排布問題之所以難解，核心原因在于可選排布方案數(shù)量極為龐大。示例中部分人員相處限制嚴(yán)格，僅能和兩人相鄰，尚且容易判斷結(jié)果；倘若人數(shù)擴(kuò)充至千人，多數(shù)人可相鄰人數(shù)多達(dá)四百人，每確定一位就餐人員，后續(xù)都會衍生出海量選擇，極易陷入繁雜的方案篩選當(dāng)中。面對這類復(fù)雜難題，最便捷的解決方式便是借助計算機(jī)運算。

接下來我們追溯計算機(jī)理論的起源，艾倫?圖靈被公認(rèn)為現(xiàn)代計算機(jī)理論奠基人。1930年代后期，正值二十多歲的圖靈提出了圖靈機(jī)這一理論計算模型，時至今日，世間所有實體計算機(jī)的運行邏輯，依舊依托這一經(jīng)典模型，這也是我日常給本科生授課的核心內(nèi)容。

在實體計算機(jī)誕生之前，圖靈便構(gòu)想設(shè)計出這款通用型機(jī)器，可通過錄入不同指令完成各類不同任務(wù)。在這之前，市面上僅有功能單一的專用運算設(shè)備，僅能完成固定計算工作，而圖靈機(jī)打破了這一局限，可靈活切換運算任務(wù)，適配多元化運算需求。在各類運算問題當(dāng)中，最基礎(chǔ)的便是僅有是或否兩種答案的判定類問題，無需輸出復(fù)雜結(jié)果。

1936年圖靈通過嚴(yán)謹(jǐn)論證證實，存在大量僅有是非答案的數(shù)學(xué)判定問題，這類看似常規(guī)的運算問題，依靠任何計算機(jī)都永遠(yuǎn)無法完成求解。這一研究成果徹底顛覆了二十世紀(jì)數(shù)學(xué)界的研究思維，數(shù)學(xué)研究不再只聚焦于如何解題，而是開始探究問題本身是否具備可解性。

圖靈通過具象實例佐證了這一結(jié)論：不存在任何一款通用程序，能夠檢測所有程序在錄入指定輸入內(nèi)容后，究竟會正常終止運行，還是陷入無限循環(huán)。日常使用電子設(shè)備時出現(xiàn)的卡頓卡死、頁面加載停滯等現(xiàn)象，從數(shù)學(xué)理論層面而言便是無法徹底規(guī)避的，我們無法編寫統(tǒng)一程序提前預(yù)判所有程序的運行終止?fàn)顟B(tài)。

這個結(jié)論聽起來難免讓人覺得消極，不過后續(xù)我們還有更多積極的研究內(nèi)容。這類無法求解的問題被統(tǒng)稱為不可判定問題，依托該結(jié)論，學(xué)界還推導(dǎo)出了大量同類不可判定難題。

舉個趣味實例，卡牌游戲萬智牌便屬于不可判定問題，該游戲可不斷擴(kuò)充卡牌卡組，對局規(guī)模沒有上限，從理論層面無法判定對局玩家是否存在必勝策略，這也是學(xué)界已經(jīng)證實的定論。

如今量子計算機(jī)備受各界關(guān)注，這里補充一項核心理論：圖靈機(jī)相關(guān)定理同樣適用于量子計算機(jī)。也就是說，傳統(tǒng)計算機(jī)無法求解的問題，量子計算機(jī)同樣無法完成求解，二者不存在本質(zhì)層面的能力差距，后續(xù)我會再詳細(xì)講解量子計算機(jī)的相關(guān)應(yīng)用。

1930年代奠定計算機(jī)理論基礎(chǔ)之后，一方面學(xué)界陸續(xù)證實諸多問題均屬于不可判定問題，另一方面實體計算機(jī)逐步落地投入使用。人們漸漸意識到，即便部分問題具備可解性，若完成運算需要耗費數(shù)百年時間，在實際應(yīng)用中依舊等同于無解。因此運算耗時成為衡量問題求解難度的核心標(biāo)準(zhǔn)。

密碼學(xué)領(lǐng)域正是依托高難度運算難題搭建安全體系，而在日常科研當(dāng)中，明確問題的實際運算耗時，也能幫助我們放棄追求完美最優(yōu)解，轉(zhuǎn)而探尋貼合實際的近似最優(yōu)解。接下來我們講解衡量運算難度的具體方式。

以三位數(shù)加法運算為例，運算流程僅為逐位對應(yīng)相加，個位、十位、百位依次運算，進(jìn)位運算難度極低，幾乎可以忽略不計。由此可見，數(shù)字加法運算的工作量，僅和數(shù)字位數(shù)成正比。再回顧多位數(shù)乘法運算，運算流程需要將兩個數(shù)字每一位數(shù)值兩兩相乘，再完成錯位疊加求和。由此能夠得出，乘法運算的工作量，和兩個數(shù)字位數(shù)的乘積成正比。基于這類規(guī)律，學(xué)界劃分出P類問題，這類問題的運算耗時，能夠通過輸入規(guī)模的多項式函數(shù)進(jìn)行界定。

簡單來說，運算耗時僅為輸入規(guī)模的固定次方級別，加法對應(yīng)一次方，乘法對應(yīng)二次方。該概念由杰克?埃德蒙茲于1970年代正式確立，他提出P類問題就是能夠在合理時長內(nèi)順利完成求解的問題。

很多人會認(rèn)為多項式函數(shù)增長速度同樣很快，我們選取運算效率偏低的五次方多項式函數(shù)，再對比指數(shù)函數(shù) 2?，以計算機(jī)每秒完成一千次運算為基準(zhǔn)進(jìn)行測算。當(dāng)輸入規(guī)模數(shù)值較小時，二者運算耗時差距并不明顯；隨著輸入規(guī)模逐步擴(kuò)大，差距會迅速拉開。輸入規(guī)模達(dá)到三十時，五次方多項式運算需要耗費近七個小時，而指數(shù)運算需要耗費十二天；當(dāng)輸入規(guī)模擴(kuò)充至一百時，多項式運算耗時約一百一十五天，指數(shù)運算更是需要長達(dá)十七個世紀(jì)。

由此能夠清晰看出，一旦輸入數(shù)據(jù)規(guī)模變大，指數(shù)級運算耗時會達(dá)到完全無法落地應(yīng)用的程度，即便聯(lián)動多臺設(shè)備協(xié)同運算也難以落地，若繼續(xù)擴(kuò)大數(shù)據(jù)規(guī)模，難度更是會無限攀升。判定問題難度，核心就是測算計算機(jī)對應(yīng)的運算耗時，我們必須依托大規(guī)模同類問題進(jìn)行判定，單一固定答案的問題不具備參考價值。

接下來我們結(jié)合實際應(yīng)用場景，講解高難度運算問題的實用價值。談及圖靈，除了計算機(jī)理論開創(chuàng)者之外，在英國民眾心中，他最為人熟知的成就便是破譯恩尼格瑪密碼，這份貢獻(xiàn)對二戰(zhàn)戰(zhàn)局走向起到了至關(guān)重要的作用。

恩尼格瑪機(jī)是二戰(zhàn)時期德軍使用的核心加密設(shè)備，圖靈借助自研運算設(shè)備成功破解該密碼體系。如今這套加密方式早已被淘汰，現(xiàn)代主流加密邏輯依托單向易運算、反向難推演的數(shù)學(xué)難題搭建而成。

我們以質(zhì)數(shù)相關(guān)運算舉例，質(zhì)數(shù)是大于1，僅能被1和自身整除的整數(shù)，2、3、5都屬于典型質(zhì)數(shù)，古希臘時期學(xué)界便已證實質(zhì)數(shù)的數(shù)量是無窮無盡的。合數(shù)則與之相反，存在除1和自身之外的其他因數(shù)，例如4、6等數(shù)字。

判定小數(shù)字是否為質(zhì)數(shù)十分簡單，而判定超大數(shù)值是否為質(zhì)數(shù)、完成大數(shù)質(zhì)因數(shù)分解，卻是各類計算設(shè)備都難以快速完成的難題。

日常線上金融通信便是依托這一原理搭建安全體系：銀行對外公開由兩個大質(zhì)數(shù)相乘得出的超大合數(shù)，大眾利用該公開數(shù)值完成信息加密并發(fā)送至銀行，銀行憑借私密的兩個質(zhì)數(shù)值，解密讀取通信內(nèi)容，整套加密體系的核心，就是大數(shù)相乘運算簡單，質(zhì)因數(shù)分解運算難度極高。

再分享一項工業(yè)生產(chǎn)領(lǐng)域的實際調(diào)度難題：工廠配備三臺生產(chǎn)設(shè)備，一夜之間積壓大量待加工訂單，需要在四百八十分鐘內(nèi)完成所有訂單加工，規(guī)劃合理的訂單分配方案。面對這類調(diào)度問題，行業(yè)內(nèi)普遍采用回溯搜索算法求解，這也是我此前研究人工智能領(lǐng)域時重點鉆研的核心算法之一。

算法實操流程為先優(yōu)先給第一臺設(shè)備分配加工訂單，直至設(shè)備工時用盡，再依次分配其余設(shè)備訂單。若分配方案最終無法完成全部訂單加工，就撤銷最后一步訂單分配選擇，重新調(diào)整排布方案，反復(fù)試錯調(diào)整，直至匹配出符合工時要求的最優(yōu)排布方式。

這類算法和大家破解數(shù)獨謎題的思路高度相似，先暫定答案試算推演，出現(xiàn)矛盾后推翻重來，不斷篩選可行方案。無論搭配何種優(yōu)化策略，核心依舊是不斷試錯排查，遍歷大部分可行方案尋找最優(yōu)解。

講解完以上內(nèi)容，我們正式引入經(jīng)典的P vs NP難題。P類問題即多項式時間內(nèi)可求解的問題，也就是現(xiàn)實當(dāng)中能夠高效完成求解的各類問題。NP并非指代無解問題，其全稱是非確定性多項式時間問題，通俗來講，判定類NP問題滿足這樣一個核心特征：若問題存在可行答案，那么這份答案能夠在多項式時間內(nèi)快速完成核驗，但是我們暫時沒有高效方式自主推導(dǎo)出這份答案。

所有P類問題都隸屬于NP問題范疇，我們既能自主快速求解，自然也能快速核驗答案正誤。此前講到的家庭座次排布問題、大數(shù)質(zhì)因數(shù)分解問題、工廠訂單調(diào)度問題，都屬于典型的NP問題。我們很難快速自主規(guī)劃出合理方案，但只要給出現(xiàn)成排布方案、分解結(jié)果與調(diào)度計劃，就能立刻核驗方案是否成立。在實際應(yīng)用當(dāng)中，絕大多數(shù)NP類難題，目前都只能依靠回溯搜索這類試錯方式求解，僅能處理小規(guī)模簡單案例，不存在通用高效的自主求解方法。

2000年，克雷數(shù)學(xué)研究所為迎接千禧之年，甄選七大頂尖數(shù)學(xué)未解難題，為每道難題設(shè)立一百萬美金懸賞獎金，P是否等于NP這一難題便位列其中。該難題直白釋義為：倘若一道問題的答案能夠快速核驗，那么是否必然存在對應(yīng)的高效解題思路，實現(xiàn)快速自主求解。

截至目前，七大千禧年難題當(dāng)中，僅有龐加萊猜想已經(jīng)完成證明，其余難題依舊懸而未決。倘若能夠證實P等同于NP，找到通用高效的NP問題求解算法，不僅能夠快速核驗各類數(shù)學(xué)證明過程，還能依托計算機(jī)自主推導(dǎo)完成數(shù)學(xué)命題證明，甚至有機(jī)會順勢攻克其余六大千禧年難題。

接下來我們講解NP完全問題的定義：所有隸屬于NP范疇的問題，只要找到其中任意一道NP完全問題的多項式時間求解算法，就等同于證實P等于NP，所有NP問題都能實現(xiàn)高效求解。該理論（Cook-Levin定理）由史蒂文?庫克與倫納德?萊文兩位學(xué)者各自獨立證實，在正式定名之前，二人便已經(jīng)證實了這類核心難題的存在。

現(xiàn)代計算機(jī)與復(fù)雜性理論奠基人之一高德納（即唐納德?克努特），在1974年面向?qū)W界征集這類難題的正式名稱，最終確定命名為NP完全問題，這個名稱偏向?qū)I(yè)晦澀，并未達(dá)到他的預(yù)期，但最終被學(xué)界沿用至今。他還曾公開表示，自己深耕相關(guān)領(lǐng)域多年，始終認(rèn)為P等同于NP的可能性微乎其微，甚至公開許諾，除官方百萬美金獎金之外，額外贈送一只活火雞，獎勵成功證明該命題的學(xué)者。

此前講到的家庭圍桌座次排布問題、工廠生產(chǎn)訂單調(diào)度問題，都屬于典型的NP完全問題，只要攻克其中任意一道難題，就能斬獲克雷數(shù)學(xué)研究所懸賞獎金，證實P與NP等價。而大數(shù)質(zhì)因數(shù)分解問題，學(xué)界普遍認(rèn)定其并不屬于NP完全問題。

再回到量子計算機(jī)的相關(guān)應(yīng)用，1994年彼得?肖爾（Peter Shor）研發(fā)出適配大數(shù)質(zhì)因數(shù)分解的量子算法。量子計算機(jī)可以依托量子比特，同步模擬海量運算設(shè)備并行運算，運算效率遠(yuǎn)超傳統(tǒng)計算機(jī)。一旦量子計算機(jī)技術(shù)成熟落地，現(xiàn)有的主流質(zhì)數(shù)加密體系將會徹底失效。

谷歌官方早已發(fā)布相關(guān)行業(yè)預(yù)警，明確提及量子計算時代即將到來，各大企業(yè)已經(jīng)著手將電子設(shè)備安全加密方式，逐步替換為能夠抵御量子攻擊的新型體系，并且定下2029年為關(guān)鍵轉(zhuǎn)型節(jié)點，足以看出這項技術(shù)帶來的行業(yè)變革迫在眉睫。

不過目前學(xué)界尚未研發(fā)出能夠求解NP完全問題的量子算法，也有相關(guān)研究佐證這類難題很難依托量子計算實現(xiàn)高效求解。簡單總結(jié)來說，量子計算機(jī)能夠優(yōu)化部分高難度非NP完全問題的運算效率，但無法撼動P對NP這一核心難題的研究格局。

接下來我結(jié)合自身研究方向展開講解，我此前深耕人工智能領(lǐng)域時，長期研究依托對稱性優(yōu)化搜索算法，以此提升調(diào)度排布類難題的求解效率。

圖同構(gòu)問題是我長期鉆研的重點研究方向，結(jié)合此前講解的圖論基礎(chǔ)，圖同構(gòu)問題就是判定兩張頂點、邊線構(gòu)成的關(guān)系圖，拋開頂點命名差異后，二者整體結(jié)構(gòu)是否完全一致。即便兩張關(guān)系圖畫法不同、頂點標(biāo)注名稱不同，只要能夠一一匹配對應(yīng)頂點位置，邊線連接關(guān)系完全吻合，就可以判定兩張圖屬于同構(gòu)圖。

該問題同樣隸屬于NP問題范疇，他人給出頂點對應(yīng)關(guān)系后，我們能夠快速核驗判定結(jié)果是否正確，但目前依舊沒有通用的多項式時間高效求解算法。學(xué)界普遍認(rèn)為該問題不屬于NP完全問題，是介于P類問題與NP完全問題之間的中間難度問題，存在極高的實際應(yīng)用價值，但其具體運算難度至今沒有精準(zhǔn)定論。

對稱性是剖析圖同構(gòu)問題難度的核心切入點，圖形對稱變換就是在不改變圖形整體結(jié)構(gòu)的前提下，調(diào)換內(nèi)部元素位置。部分簡易關(guān)系圖存在明顯對稱特征，可自由調(diào)換部分頂點位置且不改變整體連線結(jié)構(gòu)，固定唯一特殊頂點后，就能快速鎖定所有元素排布位置，大幅降低判定難度。

對稱性特征同樣能夠作用于此前講解的各類實際難題：存在對稱特征的家庭人員相處關(guān)系圖，能夠快速判定落座方案是否可行；工時一致的生產(chǎn)訂單、規(guī)格統(tǒng)一的生產(chǎn)設(shè)備，也能依托對稱特征簡化調(diào)度排布流程。反之，打破對稱特征，就會直接提升問題求解難度。

圖同構(gòu)問題的求解難度，和圖形結(jié)構(gòu)拆分形式、頂點邊線分布特征息息相關(guān)。結(jié)構(gòu)拆分清晰、頂點連接邊線數(shù)量差異化明顯的圖形，同構(gòu)判定難度更低；整體結(jié)構(gòu)高度統(tǒng)一、對稱特征極強的圖形，判定難度會大幅提升。1980年代有學(xué)者證實，攻克圖同構(gòu)問題，核心就是探尋單一關(guān)系圖的所有對稱變換形式，重點攻克原始群結(jié)構(gòu)下的圖形對稱問題即可。

2016年巴比（Babai）取得該領(lǐng)域重大研究突破，證實圖同構(gòu)問題能夠借助擬多項式時間算法完成求解。擬多項式函數(shù)的增長速度，介于普通多項式函數(shù)與指數(shù)函數(shù)之間，運算耗時遠(yuǎn)低于回溯搜索這類指數(shù)級運算方式。后續(xù)還有學(xué)者持續(xù)優(yōu)化算法參數(shù)，不斷壓縮擬多項式運算的耗時系數(shù)，如今縮減核心系數(shù)數(shù)值，依舊是該領(lǐng)域極具研究價值的前沿方向，若系數(shù)能夠無限趨近于1，該算法就會無限貼近標(biāo)準(zhǔn)多項式算法。

最后我們總結(jié)攻克千禧年難題、贏取百萬獎金的兩種研究方向。

其一，證實P等同于NP，只需找到任意一道NP完全問題的多項式時間通用求解算法即可。一旦完成證明，不僅能夠?qū)崿F(xiàn)大數(shù)快速質(zhì)因數(shù)分解，擺脫對量子加密算法的依賴，交通調(diào)度、日程規(guī)劃、資源統(tǒng)籌等所有NP類實際難題都能實現(xiàn)高效求解，徹底改變當(dāng)下的運算科研格局，甚至順勢攻克其余六大千禧年數(shù)學(xué)難題。不過這項研究成果一旦問世，勢必會影響全球各類安全加密體系，相關(guān)領(lǐng)域相關(guān)機(jī)構(gòu)也會高度關(guān)注這項研究進(jìn)展。

其二，證實P不等于NP，只需證明任意一道NP范疇內(nèi)的問題，不存在任何多項式時間高效求解算法即可。目前絕大多數(shù)數(shù)學(xué)界學(xué)者都更傾向于認(rèn)同這一結(jié)論，這也是當(dāng)下學(xué)界的主流觀點。多年以來，無數(shù)研究者嘗試為NP完全問題搭建高效算法，最終均以失敗告終。而目前最大的研究困境在于，學(xué)界依舊沒有成熟嚴(yán)謹(jǐn)?shù)恼撟C方法，能夠直接證實一類問題不存在高效求解方案，想要完成這項證明，還需要誕生堪比圖靈機(jī)理論的全新顛覆性數(shù)學(xué)思想。

大家也可以選取自己感興趣的中間難度數(shù)學(xué)問題展開研究，例如深入鉆研圖同構(gòu)問題，嘗試論證其不存在多項式時間求解算法，同樣能夠完成相關(guān)命題證明。

我的本場講座內(nèi)容到此結(jié)束，再次感謝各位的認(rèn)真聆聽。

Q&A 問答環(huán)節(jié)

主持人：

非常感謝科爾瓦教授帶來這場精彩絕倫的講座，相信在場所有人都收獲滿滿。接下來我們進(jìn)入問答交流環(huán)節(jié)。正如教授所言，倘若在座各位已經(jīng)構(gòu)思出P對NP難題的證明思路，還請謹(jǐn)慎斟酌。線上觀看直播的觀眾依舊可以掃描二維碼提交問題，現(xiàn)場觀眾舉手即可，我們會依次傳遞麥克風(fēng)收集問題。

現(xiàn)場第一位提問者：

您好，非常感謝這場干貨滿滿的講座。我并非專業(yè)數(shù)學(xué)研究者，目前正在為英國皇家藝術(shù)學(xué)會撰寫相關(guān)文稿，該學(xué)會擁有三萬余名會員，當(dāng)下最大的難題就是搭建完善的會員社交聯(lián)絡(luò)體系，為此我查閱了大量同類高難度統(tǒng)籌問題相關(guān)資料。在查閱資料的過程中，我接觸到卡爾?弗里斯頓依托貝葉斯推理搭建的數(shù)學(xué)推演理論，其論文當(dāng)中的專業(yè)代數(shù)推導(dǎo)內(nèi)容我無法自主解讀，但借助人工智能工具，我能夠梳理論文自然語言核心觀點，再拆解理解代數(shù)推導(dǎo)邏輯，重新研讀專業(yè)學(xué)術(shù)論文。我想請教您，站在專業(yè)數(shù)學(xué)研究者的角度來看，人工智能輔助解讀學(xué)術(shù)內(nèi)容、賦能人類科研思考的模式，是否會從根本上改變整個數(shù)學(xué)領(lǐng)域的研究思維與發(fā)展格局？

答：

我由衷希望人工智能能夠打破大眾對數(shù)學(xué)的刻板印象，消解普通民眾對數(shù)學(xué)的畏懼心理。日常社交當(dāng)中，每當(dāng)我告知他人自己是數(shù)學(xué)研究者，絕大多數(shù)人的第一反應(yīng)都是坦言自己學(xué)生時代數(shù)學(xué)成績不佳，倘若人工智能能夠改善這一現(xiàn)狀，便是極具價值的積極作用。

在學(xué)術(shù)證明研究領(lǐng)域，目前僅頂尖專業(yè)科研團(tuán)隊能夠借助定制化人工智能工具輔助推導(dǎo)證明；普通本科生借助通用人工智能完成課程習(xí)題解答，得出的答案依舊存在大量邏輯漏洞。

人工智能擅長文字梳理、文獻(xiàn)檢索工作，能夠快速檢索數(shù)十年前冷門學(xué)術(shù)論文當(dāng)中可用的引理結(jié)論，實現(xiàn)學(xué)術(shù)觀點整合歸納，這也是目前人工智能在數(shù)學(xué)領(lǐng)域最核心的實用價值。

但通用人工智能尚不具備嚴(yán)謹(jǐn)自主邏輯推演能力，僅能整合現(xiàn)有文字內(nèi)容輸出觀點，暫時無法獨立攻克 P 對 NP 這類核心數(shù)學(xué)難題。

整體而言，人工智能能夠成為數(shù)學(xué)科普、學(xué)術(shù)調(diào)研的優(yōu)質(zhì)輔助工具，但短期內(nèi)依舊無法取代人類學(xué)者的核心科研思維。

現(xiàn)場第二位提問者：

您好，聽完本次講座我有一個疑問，哥德巴赫猜想、孿生素數(shù)猜想這類經(jīng)典數(shù)論未解難題，是否能夠套用今晚講解的 P與NP 相關(guān)理論進(jìn)行研究分析？

答：

這類數(shù)論猜想和我們今晚探討的判定類是非問題不屬于同一范疇，這類猜想是針對無窮多自然數(shù)提出的整體性命題，無法直接劃入 P 類與 NP 類問題的劃分體系當(dāng)中。

二者唯一的關(guān)聯(lián)點在于，倘若證實 P 等同于 NP，人類能夠依托計算機(jī)快速完成數(shù)學(xué)命題證明推導(dǎo)，屆時便有機(jī)會借助機(jī)器運算完成這類數(shù)論猜想的完整證明，但這套理論無法直接用于推進(jìn)猜想研究進(jìn)程。

不過當(dāng)下已有學(xué)者依托超大范圍計算機(jī)輔助運算，證實了弱版哥德巴赫猜想，也就是奇數(shù)三素數(shù)之和定理。研究者借助計算機(jī)完成海量數(shù)值驗算，劃定小范圍數(shù)值成立依據(jù)，再通過純數(shù)學(xué)推導(dǎo)證實超大數(shù)值區(qū)間內(nèi)命題成立，完成整套證明流程。這類計算機(jī)輔助證明，依托的是固定單次運算程序，并非可反復(fù)通用的多項式算法。

現(xiàn)場第三位提問者：

您好，我了解到有相關(guān)研究證實，菌群能夠自主求解旅行商（TSP）這類統(tǒng)籌規(guī)劃難題，想請教這類依托自然生物規(guī)律形成的運算模式，是和大數(shù)分解問題一樣屬于中間難度問題，還是能夠成為攻克指數(shù)級難度難題的全新思路？

答：

旅行商問題是典型的NP完全問題，想要高效求解這類難題，各類新型運算模式的核心邏輯基本都是大規(guī)模并行運算，依托海量運算單元同步試錯推演，依靠數(shù)量優(yōu)勢壓縮整體運算時長。這類自然生物形成的自主統(tǒng)籌模式，能夠快速處理小規(guī)模簡易案例，但無法形成通用規(guī)律適配所有場景，依舊存在部分特殊案例難以順利求解。我對菌群相關(guān)專項研究了解不多，但從復(fù)雜性理論角度來看，這類模式僅能優(yōu)化局部運算效率，無法從根本上解決NP完全問題的核心研究困境。

線上觀眾提問一：

能否在講座內(nèi)容當(dāng)中補充提及埃達(dá)?洛夫萊斯？

答：

非常樂意補充介紹。埃達(dá)?洛夫萊斯是計算機(jī)發(fā)展史上不可或缺的先驅(qū)人物，她最早為查爾斯?巴貝奇設(shè)計的分析機(jī)編寫運算程序，這份研究成果也成為圖靈機(jī)理論誕生的重要思想鋪墊。她的研究成果擁有極高的歷史地位，理應(yīng)收獲更多學(xué)界贊譽，不過其研究聚焦于早期程序編寫，尚未涉及運算時長、問題難度判定等相關(guān)研究內(nèi)容，因此本場講座未做重點講解，非常感謝這位觀眾的提醒。

線上觀眾提問二：

您提到大數(shù)質(zhì)因數(shù)分解不屬于NP完全問題，倘若證實P等同于NP，是否所有NP范疇內(nèi)的問題都會成為NP完全問題？

答：

沒錯，一旦證實P與NP完全等價，所有NP問題的求解難度將會趨于統(tǒng)一，自然不再區(qū)分中間難度問題與NP完全問題。在目前未完成證明的前提下，學(xué)界依舊將大數(shù)分解、圖同構(gòu)這類問題劃定為中間難度問題，難度介于標(biāo)準(zhǔn)P類問題與NP完全問題之間。

現(xiàn)場第四位提問者：

您好，拋開量子計算機(jī)不談，依托當(dāng)下高速迭代升級的通用人工智能，未來是否會出現(xiàn)人工智能自主破解 P對NP 難題，卻刻意隱瞞研究成果的情況？

答：

從技術(shù)層面來講這種情況基本不可能發(fā)生。當(dāng)下主流生成式人工智能的核心優(yōu)勢集中在學(xué)術(shù)文獻(xiàn)檢索、觀點整合梳理、科普內(nèi)容撰寫等領(lǐng)域，能夠快速挖掘冷門學(xué)術(shù)成果、整合多方研究思路，這也是目前人工智能在數(shù)學(xué)領(lǐng)域最核心的突破點。

但這類人工智能缺乏嚴(yán)謹(jǐn)自主邏輯推導(dǎo)能力，無法自主搭建完整的數(shù)學(xué)證明體系，甚至無法自主判別自身輸出內(nèi)容的正誤，所有和數(shù)學(xué)證明相關(guān)的輸出內(nèi)容，都必須依靠專業(yè)研究者逐一核驗、修正。當(dāng)下人工智能僅能作為科研輔助工具，距離自主攻克頂尖數(shù)學(xué)核心難題，還有極為遙遠(yuǎn)的距離。

主持人：

由于時間有限，本場公開問答環(huán)節(jié)到此結(jié)束。大家若是還有其余問題，可短暫停留現(xiàn)場，和教授私下交流探討。再次感謝各位蒞臨格雷沙姆學(xué)院參與本次學(xué)術(shù)活動，感謝倫敦數(shù)學(xué)會的通力合作，也再次由衷感謝科爾瓦?羅尼 - 杜加爾教授帶來這場極具深度與趣味性的精彩講座。

參考資料

https://www.gresham.ac.uk/watch-now/hard-complexity

https://www.youtube.com/watch?v=y9G_8_JItdc

小樂數(shù)學(xué)科普近期文章

版權(quán)聲明：本文首發(fā)于微信公眾號“zzllrr小樂”的專欄《小樂數(shù)學(xué)科普》。歡迎個人轉(zhuǎn)發(fā)。如需轉(zhuǎn)載，請在“zzllrr小樂”公眾號后臺回復(fù)“轉(zhuǎn)載”，還可通過公眾號菜單、發(fā)送郵件到zzllrr@gmail.com與我們?nèi)〉寐?lián)系。相關(guān)圖文音視頻內(nèi)容默認(rèn)遵守CC BY-NC 4.0知識共享協(xié)議，未獲作者和譯者授權(quán)，禁止用于營銷宣傳和商業(yè)目的。

·開放 · 友好 · 多元 · 普適 · 守拙·

讓數(shù)學(xué)

更加

易學(xué)易練

易教易研

易賞易玩

易見易得

易傳易及

歡迎評論、點贊、在看、在聽

收藏、分享、轉(zhuǎn)載、投稿

查看原始文章出處

點擊底部一起捐

助力騰訊公益

點擊zzllrr小樂

公眾號主頁

右上角

置頂★加星

數(shù)學(xué)科普不迷路！