LLM、教科書的手がかり排除の難問で苦戦か P/NP完全問題の性能比較で判明
ヌルル・ラビブ・サイエディ (Nurul Labib Sayeedi) らは2026年10月21日(現地時間)、LLM (大規模言語モデル) がNP完全問題 (NPC問題) において、対応する多項式時間 (P) 問題よりも低い正答率を示す研究結果をarXivで発表した。既存のベンチマークが問題の複雑性クラスを区別できない点を踏まえ、P2NPCベンチ (P2NPCBench) と呼ばれる新たなベンチマークを導入し、モデルの推論能力を評価した。