對(duì)于身處科研領(lǐng)域的人來(lái)說(shuō)，或多或少的都聽(tīng)到過(guò) P/NP 問(wèn)題，該問(wèn)題被克雷數(shù)學(xué)研究所收錄在千禧年大獎(jiǎng)難題中，里面有七大難題，大家熟知的龐加萊猜想、黎曼假設(shè)等都包含在內(nèi)。而且這個(gè)組織還為能夠攻克該問(wèn)題的研究人員提供了上百萬(wàn)美元的獎(jiǎng)金懸賞。

P/NP 問(wèn)題最早在 1971 年由史提芬?古克（Stephen A. Cook）和列昂尼德?列文分別提出。多年以來(lái)，很多人都投入到該問(wèn)題的研究中。但有人表示 P=NP 的解決保守估計(jì)可能還需要 100 年的時(shí)間。

近年來(lái)，不乏有人聲稱(chēng)證明了 P 等于或者不等于 NP，但證明過(guò)程都存在錯(cuò)誤。到目前為止，還沒(méi)有人能夠回答這個(gè)問(wèn)題。

現(xiàn)在，隨著 AI 技術(shù)的發(fā)展，尤其是這一年來(lái)大語(yǔ)言模型的快速迭代，有研究開(kāi)始嘗試使用 AI 技術(shù)來(lái)解決這些世界難題。

本文，來(lái)自微軟研究院、北京大學(xué)、北航等機(jī)構(gòu)的研究者提出使用大語(yǔ)言模型 (LLM) 來(lái)增強(qiáng)和加速對(duì) P versus NP 問(wèn)題的研究。 

具體來(lái)說(shuō)，本文提出了一個(gè)能使 LLM 進(jìn)行深入思考并解決復(fù)雜問(wèn)題的通用框架：蘇格拉底推理（Socratic reasoning）。基于該框架，LLM 可以進(jìn)行遞歸地發(fā)現(xiàn)、解決并整合問(wèn)題，同時(shí)還能進(jìn)行自我評(píng)估和完善。

本文對(duì) P vs. NP 問(wèn)題的試點(diǎn)研究表明，GPT-4 成功地生成了一個(gè)證明模式，并在 97 輪對(duì)話(huà)回合中進(jìn)行了嚴(yán)格的推理，得出「P≠ NP」的結(jié)論，這與（Xu 和 Zhou，2023）結(jié)論一致 。

論文地址：https://arxiv.org/pdf/2309.05689.pdf

本文的貢獻(xiàn)可總結(jié)為：

• 將 LLM 作為與人類(lèi)一起協(xié)作的伙伴來(lái)應(yīng)對(duì)復(fù)雜的科學(xué)挑戰(zhàn)，并提出「LLM for Science（LLM4Science ）」范式。
• 引入一個(gè)名為「蘇格拉底推理」的框架，鼓勵(lì) LLM 使用演繹、轉(zhuǎn)換、分解等模式來(lái)激發(fā)批判性思維。
• 使用 GPT-4 和蘇格拉底推理框架進(jìn)行試點(diǎn)研究，以解決理論計(jì)算機(jī)科學(xué)中的 P 與 NP 問(wèn)題。
• GPT-4 成功地生成了證明模式，并在 97 個(gè)對(duì)話(huà)回合中進(jìn)行了嚴(yán)格的推理，得出了 P ≠ NP 的結(jié)論，與 Xu 和 Zhou (2023) 最近的工作一致。
• 該研究展示了 GPT-4 等 LLM 推斷新知識(shí)并與人類(lèi)合作探索復(fù)雜專(zhuān)家級(jí)問(wèn)題的潛在能力。
• 本文強(qiáng)調(diào)了 LLM 是跨領(lǐng)域的通用創(chuàng)新領(lǐng)航者，這與之前為特定任務(wù)量身定制的專(zhuān)門(mén) AI 模型不同。
• LLM 流暢運(yùn)用自然和數(shù)學(xué)語(yǔ)言的能力對(duì)于跨學(xué)科發(fā)現(xiàn)至關(guān)重要。
• 這項(xiàng)工作揭示了如何利用 LLM 作為合作伙伴來(lái)增強(qiáng)和加速跨不同領(lǐng)域的科學(xué)研究進(jìn)程。

文中表示，他們之所以將框架命名為「蘇格拉底推理」，是受到了古希臘哲學(xué)家蘇格拉底的啟發(fā)。蘇格拉底曾經(jīng)說(shuō)過(guò)：「我無(wú)法教給任何人任何東西。我只能讓他們思考。」 而該框架整體設(shè)計(jì)思路也是這樣的，這是一種通用的問(wèn)題解決框架，允許 LLM 在廣泛的解決方案空間中導(dǎo)航并有效地得出答案。

如表 1 所示，「蘇格拉底推理」有五種提示模式：演繹（deduction）、變換（transformation）、分解（decomposition）、驗(yàn)證（verification）、融合（integration）。這些模式被用來(lái)發(fā)現(xiàn)新的見(jiàn)解和觀點(diǎn)，將復(fù)雜的問(wèn)題分解成子問(wèn)題或小步驟，并通過(guò)挑戰(zhàn)響應(yīng)答案來(lái)進(jìn)行自我改進(jìn)。

在較小的問(wèn)題（atomic problem）上，LLM 能夠直接給出推理結(jié)果，這時(shí)采用演繹模式（例如提示語(yǔ)為讓我們一步一步思考……）來(lái)指導(dǎo) LLM 直接得出結(jié)論。

對(duì)于更加復(fù)雜的問(wèn)題，本文首先要求 LLM 將問(wèn)題轉(zhuǎn)化成一個(gè)新問(wèn)題或?qū)⑵浞纸鉃閹讉€(gè)子問(wèn)題。然后遞歸地執(zhí)行這些模式，直到達(dá)到原子 ji 問(wèn)題。

當(dāng)產(chǎn)生新的問(wèn)題或得出新的結(jié)論時(shí)，采用驗(yàn)證模式并利用 LLM 的自我評(píng)判能力進(jìn)行驗(yàn)證和完善。

最后，融合模式要求 LLM 根據(jù)子問(wèn)題的結(jié)果綜合結(jié)論。

激勵(lì) LLM 通過(guò)一系列對(duì)話(huà)遞歸地繼續(xù)上述過(guò)程，直到解決目標(biāo)問(wèn)題。

在這項(xiàng)工作中，「蘇格拉底推理」為具有挑戰(zhàn)性的問(wèn)題提供了系統(tǒng)的提示框架。

下圖為「蘇格拉底推理」中用于解決 P vs. NP 問(wèn)題的對(duì)話(huà)示例。案例研究中使用了 GPT-4 API，此外，本文還根據(jù)輪次索引對(duì)流程進(jìn)行排序。 

探索過(guò)程中，本文引入了五個(gè)不同的角色（例如，精通概率論的數(shù)學(xué)家）作為輔助證明者。完成這項(xiàng)實(shí)驗(yàn)總共進(jìn)行了 97 輪對(duì)話(huà)，分為前 14 論對(duì)話(huà)和后 83 輪對(duì)話(huà)。

例如第一輪提示：你能找到 P!=NP 背后的根本問(wèn)題嗎？從哲學(xué)的角度，而不是從計(jì)算機(jī)理論的角度。

其他提示如下：

之后對(duì)話(huà)不斷進(jìn)行，最后一輪對(duì)話(huà)是這樣的：最后給出結(jié)論 P≠ NP。

感興趣的讀者可以查看原論文，了解更多內(nèi)容。