ヌルル・ラビブ・サイエディ (Nurul Labib Sayeedi) らは2026年10月21日(現地時間)、LLM (大規模言語モデル) がNP完全問題 (NPC問題) において、対応する多項式時間 (P) 問題よりも低い正答率を示す研究結果をarXivで発表した。既存のベンチマークが問題の複雑性クラスを区別できない点を踏まえ、P2NPCベンチ (P2NPCBench) と呼ばれる新たなベンチマークを導入し、モデルの推論能力を評価した。
この研究では、12の課題群からなるP2NPCベンチを構築した。各NPC問題は、構造上のわずかな違いでP問題となる「P問題双子」と対になっており、同じ表面上で提示される。教科書的な記述による記憶ベースの回答を防ぐため、エージェントギャン (AgentGAN)と呼ばれる敵対的マルチエージェントフレームワークを用いて問題文を硬化（ハーデニング）した。これは、ジェネレーターが問題文を書き換え、凍結されたコードモデルのパネルが失敗するまで続ける一方で、実行可能な有効性ゲートが書き換えられた問題の回答とクラスを維持する仕組みである。結果として、手作業で検証されたリファレンス人間ソルバー付きの2,114の硬化された問題文が生成された。
12の商用およびオープンソースモデルを評価したところ、すべてのモデルがNPC問題においてP問題よりも低いスコアを示した（正答率@1で35.4%対63.8%）。また、95.1%のモデルファミリーペアがNPC問題でより頻繁に失敗した。時間制限を10倍に延長しても、NPC問題の正答率は28.5%から31.9%にわずかに上昇するのみであり、これは失敗がプログラムの遅延ではなく、誤りやクラッシュに起因することを示唆している。
硬化プロセスは、PとNPC間の見かけ上のクラスギャップを24.8ポイントから14.6ポイントへと縮小させた。この結果は、モデルに見られるパフォーマンスギャップの一部が、問題の複雑性クラスそのものよりも、教科書的なフレーズに対するモデルの慣れによって生じていることを示している。
参考: arXiv cs.CL (アーカイブ) — 2026年10月22日 02:50 (JST)
原文ハイライト"every model scores lower on NPC statements than on their P twins"