GPT-4在97輪對話中探索世界難題，給出P≠NP結論

作者：機器之心 2023-09-14 12:34:20

人工智能新聞

這是對「LLM for Science」一次有希望的探索。

對于身處科研領域的人來說，或多或少的都聽到過 P/NP 問題，該問題被克雷數學研究所收錄在千禧年大獎難題中，里面有七大難題，大家熟知的龐加萊猜想、黎曼假設等都包含在內。而且這個組織還為能夠攻克該問題的研究人員提供了上百萬美元的獎金懸賞。

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

近年來，不乏有人聲稱證明了 P 等于或者不等于 NP，但證明過程都存在錯誤。到目前為止，還沒有人能夠回答這個問題。

現在，隨著 AI 技術的發展，尤其是這一年來大語言模型的快速迭代，有研究開始嘗試使用 AI 技術來解決這些世界難題。

本文，來自微軟研究院、北京大學、北航等機構的研究者提出使用大語言模型 (LLM) 來增強和加速對 P versus NP 問題的研究。

具體來說，本文提出了一個能使 LLM 進行深入思考并解決復雜問題的通用框架：蘇格拉底推理（Socratic reasoning）。基于該框架，LLM 可以進行遞歸地發現、解決并整合問題，同時還能進行自我評估和完善。

本文對 P vs. NP 問題的試點研究表明，GPT-4 成功地生成了一個證明模式，并在 97 輪對話回合中進行了嚴格的推理，得出「P≠ NP」的結論，這與（Xu 和 Zhou，2023）結論一致。

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

本文的貢獻可總結為：

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

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

如表 1 所示，「蘇格拉底推理」有五種提示模式：演繹（deduction）、變換（transformation）、分解（decomposition）、驗證（verification）、融合（integration）。這些模式被用來發現新的見解和觀點，將復雜的問題分解成子問題或小步驟，并通過挑戰響應答案來進行自我改進。

在較小的問題（atomic problem）上，LLM 能夠直接給出推理結果，這時采用演繹模式（例如提示語為讓我們一步一步思考……）來指導 LLM 直接得出結論。

對于更加復雜的問題，本文首先要求 LLM 將問題轉化成一個新問題或將其分解為幾個子問題。然后遞歸地執行這些模式，直到達到原子 ji 問題。

當產生新的問題或得出新的結論時，采用驗證模式并利用 LLM 的自我評判能力進行驗證和完善。

最后，融合模式要求 LLM 根據子問題的結果綜合結論。

激勵 LLM 通過一系列對話遞歸地繼續上述過程，直到解決目標問題。