GPT-4は97回の対話で世界の諸問題を探り、P≠NPという結論を導き出した。

科学研究の分野で働く人なら、P/NP 問題についてはある程度聞いたことがあるでしょう。この問題は、クレイ数学研究所のミレニアム懸賞問題に含まれていました。この中には、よく知られているポアンカレ予想やリーマン予想を含む 7 つの主要な問題が含まれています。同団体はまた、この問題を解決できる研究者に100万ドルの報奨金も提供している。

P/NP 問題は、1971 年に Stephen A. Cook と Leonid Levin によって初めて提案されました。長年にわたり、多くの人々がこの問題の研究に専念してきました。しかし、P=NP の解決には控えめに言ってもあと 100 年かかるかもしれないと言う人もいます。

近年、P が NP に等しいか等しくないかを証明したと主張する人が多数いますが、証明のプロセスに誤りがありました。今のところ、誰もこの質問に答えられていません。

現在、AI技術の発展、特に過去1年間の大規模言語モデルの急速な反復により、AI技術を使用してこれらの世界の問題を解決しようとする研究がいくつか始まっています。

この論文では、マイクロソフトリサーチ、北京大学、北京航空航天大学などの研究者が、大規模言語モデル (LLM) を使用して P 対 NP 問題の研究を強化し、加速することを提案しました。

具体的には、この論文では、LLM が深く考え、複雑な問題を解決できるようにする一般的なフレームワーク、つまりソクラテス的推論を提案しています。このフレームワークに基づいて、LLM は問題を再帰的に発見、解決、統合すると同時に、自己評価と改善も行うことができます。

P対NP問題に関する私たちのパイロット研究では、GPT-4が証明パターンを正常に生成し、97ラウンドの対話で厳密な推論を実行し、「P≠NP」という結論に達したことが示されました。これは、(Xu and Zhou、2023)の結論と一致しています。

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

この論文の貢献は次のように要約できます。

LLM は、複雑な科学的課題に対処するために人間との共同パートナーとして使用され、「科学のための LLM (LLM4Science)」パラダイムが提案されています。
LLM が演繹、変換、分解などのパターンを使用して批判的思考を刺激することを奨励するために、「ソクラテス的推論」と呼ばれるフレームワークを導入します。
GPT-4 とソクラテス推論フレームワークを使用してパイロットスタディを実施し、理論コンピュータサイエンスにおける P 対 NP 問題を解決します。
GPT-4は証明パターンを正常に生成し、97回の対話ターンで厳密な推論を実行し、P≠NPと結論付けました。これは、XuとZhou（2023）の最近の研究と一致しています。
この研究は、GPT-4 などの LLM が新しい知識を推論し、人間と協力して複雑な専門家レベルの問題を探索する可能性を示しています。
この論文では、特定のタスクに合わせて調整された従来の特殊な AI モデルとは異なり、LLM がドメイン全体にわたる汎用的なイノベーションリーダーであることを強調しています。
LLM の自然言語と数学言語を流暢に使用できる能力は、学際的な発見に不可欠です。
この研究は、LLM をパートナーとして活用して、多様な分野にわたる科学研究を強化および加速する方法を明らかにしています。

記事によると、彼らは古代ギリシャの哲学者ソクラテスにインスピレーションを受けたため、このフレームワークを「ソクラテス的推論」と名付けたとのこと。ソクラテスはかつてこう言いました。「私は誰にも何も教えることはできない。考えさせることしかできない。」このフレームワークの全体的な設計思想もこれと同じです。これは、LLM が幅広いソリューション空間をナビゲートし、効率的に答えを導き出せるようにする、一般的な問題解決フレームワークです。

表1に示すように、「ソクラテス的推論」には演繹、変換、分解、検証、統合の5つのプロンプトモードがあります。これらのパターンは、新しい洞察や視点を発見し、複雑な問題をサブ問題や小さなステップに分解し、チャレンジレスポンスの回答を通じて自己改善するために使用されます。

より小さな問題 (原子問題) では、LLM は推論結果を直接与えることができます。この場合、演繹モデル (たとえば、「ステップごとに考えてみましょう...」というプロンプト) を使用して、LLM が直接結論を導き出すようにガイドします。

より複雑な問題の場合、この論文ではまず LLM が問題を新しい問題に変換するか、いくつかのサブ問題に分解することを要求します。これらのパターンは、アトミック ji 問題に到達するまで再帰的に実行されます。

新たな疑問が生じたり、新たな結論に達したりした場合は、検証モードが採用され、LLMの自己評価能力を使用してそれらを検証し、改善します。

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

動機付け LLM は、対象の問題が解決されるまで、一連の対話を通じて上記のプロセスを再帰的に継続します。

この作品では、ソクラテス的推論が、困難な問題に対する体系的なプロンプトの枠組みを提供します。

次の図は、「ソクラテス的推論」で P 対 NP 問題を解決するために使用される対話の例です。ケーススタディでは GPT-4 API が使用され、論文ではラウンドインデックスに基づいてパイプラインをソートすることも行われました。

この論文では、調査中に、補助証明者として 5 つの異なる役割 (確率論に精通した数学者など) を紹介しています。この実験を完了するために合計 97 ラウンドの対話が実施され、最初の 14 ラウンドの対話と最後の 83 ラウンドの対話に分けられました。

たとえば、最初のラウンドのプロンプト: P!=NP の背後にある根本的な問題を見つけることができますか?コンピュータ理論の観点からではなく、哲学的な観点から。

その他のヒントは次のとおりです:

会話は続き、最後の会話は次のようになりました。最終的に、P≠NPという結論が出されました。