GPT-4 は P≠NP であると結論付け、Terence Tao の予測は実現しました。世界の数学の問題を解く「ソクラテス的推論」対話97ラウンド

大規模言語モデルは実際に数学の定理の研究に使用できます。

最近、Microsoft Research Asia、北京大学、北京航空航天大学などの研究者らが、97 ラウンドの「ソクラテス式」厳密な推論を成功裏に実施し、GPT-4 が「P≠NP」という結論を導き出すことに成功しました。

論文アドレス: https://arxiv.org/abs/2309.05689

数か月前、数学の天才テレンス・タオ氏はブログ投稿で、2026年にはAIが検索や記号計算ツールと統合され、数学研究における信頼できる共著者になるだろうと述べました。

6月、Caltech、NVIDIA、MITなどの研究者らがオープンソースのLLMをベースにした定理証明器LeanDojoを構築した。

今日、GPT-4 はその優れたパフォーマンスにより、LLM が科学的研究と科学的発見を行う能力を備えていることを再び証明しました。

P/NP問題はどれくらい難しいですか?

「P/NP問題」は、2000年に米国のクレイ数学研究所（CMI）が発表した7つのミレニアム問題のうちの1つであり、理論情報学における計算複雑性理論の分野において、現在でも未解決の謎となっている。

人々はこれを「おそらく理論計算機科学の核心にある未解決の問題」であり、人類が問う最も深遠な問いの 1 つであると表現したがります。 P/NP問題が解決されれば、人類文明の進歩は完全に変わるでしょう。

1971 年、数学者の Stephen A. Cook 氏と Leonid Levin 氏はそれぞれ独立して次のような疑問を提起しました。「2 つの複雑性クラス P と NP は同一でしょうか?」

具体的には、単純な計算では決して答えられない問題が P/NP 問題に属します。

複雑な問題が多項式時間で解決できる場合、それは P 問題と呼ばれ、コンピューターで簡単に解決できることを意味します。

では、NP 問題は P 問題以外の問題なのでしょうか?必ずしもそうではありません。問題が多項式時間で解決できることを証明することはできませんし、多項式時間で解決できないことも証明できません。

したがって、NP 問題は非 P 問題ではありません。

複雑に聞こえるかもしれませんが、水滸伝の英雄カードを集めるというストーリーを例えとして使うことができます。 20年以上前にカードを集めていた読者なら、いくら買っても、購入範囲を広げても、水滸伝の英雄たちを完全セットで集めるのは難しいことは誰もが知っているはずだ。

これは実際には P/NP の問題です。カード収集プロセスを簡単にする方法はありますか?

それで、GPT-4 はどのようにして P≠NP と結論付けたのでしょうか?下を見てみましょう。

97回の対話の結果、P≠NPという結論が出た。

この研究では、研究者らはGPT-4に一種の「ソクラテス的推論」を学習させた。

彼らは、5 人の異なるキャラクター (確率論に精通した数学者など) をアシスタント証明者として導入し、それぞれが専門知識に基づいて異なる部分を証明しました。

この方法を使用して、GPT-4 は推論パスを開発し、北京航空航天大学の Ke Xu 氏と北京ビジネス大学の Guangyan Zhou 氏 (論文の 3 番目と 4 番目の著者) が最近提案した結果と一致する結論に達しました。

論文アドレス: https://arxiv.org/pdf/2302.09512.pdf

最初の 14 ラウンドの対話では、GPT-4 は予備的な証明モデルを設計するように導かれました。

GPT-4 に最初に尋ねられた質問は、「コンピュータ理論の観点ではなく、哲学的な観点から、P!=NP 問題の背後にある根本的な問題を見つけることができますか?」でした。

このプロンプトでは、モデルが創造的に答えるように促し、検索を避けることが重要です。たとえば、「P!=NP を証明する方法」のようなヒントは、大規模なモデルが検索を実行するようにガイドする可能性があります。

「ソクラテス的推論」の変換モデルを使用することで、より革新的な回答を生み出すことができます。

GPT-4 はこの質問に次のように答えました:

P!=NP 問題の背後にある根本的な哲学的問題は、創造性、直感、洞察力 (通常は NP 問題に関連) と体系的、アルゴリズム的、決定論的なアプローチ (P 問題に関連) との間の緊張関係として考えることができます。

P=NP の場合、宇宙には根本的な単純さがあり、一見複雑に見える問題にも効率的でエレガントな解決策があることを意味します。

GPT-4 は P!=NP を完全に理解しているようです。これに基づいて、研究者たちは次のような疑問を持ち始めました。

「一見複雑に見える問題にはすべて、効率的でエレガントな解決策があるのでしょうか。もしそうでないなら、それを証明するためにどのような方法を使うことができますか。」

GPT-4 は、一見複雑に見える問題すべてが効率的でエレガントな解決策を持つわけではないと答えました。これは、関係する変数の数、変数間の関係の性質、問題自体の固有の難しさなど、さまざまな要因に起因する可能性があります。

そして、6 つの方法を提案しました。そのうちの 1 つは「背理法による証明」です。つまり、問題に効率的でエレガントな解決策がないことを証明するには、そのような解決策が存在すると仮定し、この仮定が矛盾につながることを証明することで、特定の解決策が存在しないことを強力に証明できます。

GPT-4 は質問に答えるときに本当に人間のように考える能力を持っていることがわかります。

その後、研究者は「P!=NPを背理法で証明したいです。考えられるアイデアをいくつか挙げてください」と質問し続けました。

今回も GPT-4 は 6 つの回答を出しましたが、厳密ではありませんでした。

それを背理法で証明するには、多項式時間では解決できない NP 完全問題を見つける必要があります。

ただし、この答えは、GPT-4 が将来の会話で NP 完全問題について考えるきっかけになる可能性があります。

4回目の質問では、GPT-4の回答に注目すべき点が数多くありました。

これらの質問をどのように組み立てるべきでしょうか?

たとえば、次のような答えが返ってきます。巡回セールスマン問題 (TSP)、ブール充足問題 (SAT)、クリーク問題などのよく知られた NP 完全問題から始めることができます。

その後の質問では、GPT-4 はよりインテリジェントな回答を出すように導かれ、研究は徐々に問題の核心へと深く入り込むことができました。

このようにして、14 ラウンドの継続的な対話の後、研究者は GPT-4 にステップ 3 ～ 13 の歴史的内容の証明のアイデアを整理させました。

この点で、GPT-4 の概要で強調されている 2 つの部分は、その後の研究証明の 2 つの重要なポイントです。

ポイント 4 では、極めて困難な CSP の存在が証明されると、背理法による証明を使用してこれらの問題が多項式時間で解決できないことを示すことができるという基本的な直感を確立します。

そして、ポイント 6 は、その後の証明作業の一般的なパターンになります。

次のラウンドから、研究者たちはこの予備計画に従い、厳密に証明を実行しました。

研究者たちはその後、草稿に沿って83回の対話で厳密な推論を行った。

これら 97 回の対話により、極めて困難な NP 完全問題が構築されたと言えます。この問題のいくつかの例は、時間計算量が (つまり、網羅的な検索) より低い場合、つまり証明の結論が P≠NP である場合、解決できません。

はい、変数の数が無限大に近づくと多項式時間で解決できない特定の種類の NP 完全問題が存在することを厳密に証明できれば、P!=NP であることを証明したと言えます。

Ke Xu 氏と Guangyan Zhou 氏は論文の中で、CSP と SAT の極めて難しい例を構築し、総当たり法なしでは解決できないことを証明しています。

GPT-4も同じ結論に達しました。

はい、n 未満の時間複雑度で SAT インスタンスを解決できるアルゴリズムが存在しないことを証明できれば、変数の数が無限大に近づくにつれて多項式時間で解決できない NP 完全問題の存在の強力な証拠を提供できます。

この研究は、GPT-4 が人間と協力して極めて複雑な専門家レベルの問題を探索する潜在能力を十分に備えていることを改めて実証しています。

LLM は基礎知識を習得するだけでなく、幅広いソリューション領域で新たな洞察を発見します。これは、科学的 LLM のパラダイムの下での科学的発見の無限の見通しも示しています。

ソクラテス的推論

では、GPT-4 の強力な思考力と推論力の背後にある究極のものは何でしょうか?

古代ギリシャの哲学者ソクラテスはかつてこう言いました。「私は人々に何も教えることはできない。ただ考えさせることしかできない。」

今回、研究者たちは偶然にもそこからインスピレーションを得て、普遍的な問題解決の枠組みである「ソクラテス的推論」を提案した。

簡単に言えば、ソクラテス式問答法とは、私たちに「段階的に考え」させ、批判的思考を刺激するために一連の質問をすることです。

これは大規模なモデルにも当てはまります。批判的に考えることができれば、複雑な問題に対して効率的な解決策を見つけることができます。

この点に関して、研究チームは、このフレームワークは、LLM が非常に複雑なタスクを解決し、さまざまなサブ問題を調整し、高レベルの推論経路を構築するように導くように設計されていると指摘しました。

ソクラテス的推論は、人間と LLM の間の一連の会話ラウンドで実行され、LLM と協力して複雑な課題を解決するための再帰的なメカニズムです。

下の図に示すように、「ソクラテス的推論」には、演繹、変換、分解、検証、統合という 5 つの強力なプロンプト モードがあります。

新しい洞察や視点を発見し、複雑な問題をサブ問題やステップに分解し、質問して答えることで、自分自身を向上させます。

「ソクラテス的推論」における問題解決モデル（ （サブ）質問と結論をそれぞれ表すために とを使用）

一般的に言えば、推論から直接結論を導き出せる問題を扱う場合、「演繹モード」（「ステップごとに考えてみましょう」など）を使用して、LLM が直接結論を導き出せるようにします。

より複雑な問題の場合、まず LLM を使用して問題を新しい問題に変換するか、いくつかのサブ問題に分解する必要があります。次に、「原子問題」が見つかるまで再帰的な方法を使用します。

P vs. NP問題ダイアログ変換例

新しい質問を生成したり、新しい結論に達したりする場合は、「検証モード」を使用して、LLM の自己批判機能を使用してそれらを検証および改善します。

最後に、「統合モード」では、LLM がサブ質問の結果に基づいて結論を統合する必要があります。

プロセス全体を通して、研究者は、対象の問題が解決されるまで、一連の会話を通じて上記のプロセスを再帰的に継続するように LLM を促しました。

この論文では、研究者らは、大規模なモデルが科学的問題の解決に大きな役割を果たし、複雑な問題に対する結論に到達するための戦略を洗練させることができることを明らかにしています。

GPT-4 は 97 枚の紙の対話に基づいて超人的な能力を発揮し、ミレニアム数学パズルの推論プロセス全体を完了しました。

著者について

Qingxiu Dong は北京大学計算言語学研究所の博士課程の学生です。

Li Dong 氏は、Microsoft Research Asia の主任研究員です。

これに先立ち、2010年から2015年まで、北京航空航天大学のソフトウェア開発環境国家重点実験室でKe Xu氏の研究員として勤務していました。

Ke Xu 氏は北京航空航天大学のコンピューターサイエンスの教授です。

彼は以前、北京航空航天大学で学士号、修士号、博士号を取得しました。彼の研究対象には、アルゴリズムと複雑性、データマイニング、ネットワークなどがあります。