論文の概要: Did the Problem Actually Get Harder? Testing LLMs on Paired P and NP-Complete Problems Hardened by Adversarial Multi-Agent Rewriting

• arxiv url: http://arxiv.org/abs/2610.30103v1
• Date: Wed, 21 Oct 2026 17:50:19 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-23 00:40:06.464224
• Title: Did the Problem Actually Get Harder? Testing LLMs on Paired P and NP-Complete Problems Hardened by Adversarial Multi-Agent Rewriting
• Title（参考訳）: 問題は実際より難しくなったか? 対立的多エージェント書き換えにより強化されたペアPとNP-Complete問題におけるLCMのテスト
• Abstract要約: 多くのNP完全(NPC)問題は、グラフの3色と2色のような1つの構造的な詳細で異なる時間(P)双対を持つ。 P2NPCBenchは、各NPC問題とP双対を同一表面上でペアリングする12の問題系列のベンチマークである。 我々は、リコールを可能にする教科書の手がかりを取り除くために、ジェネレータが各ステートメントをフリーズコードモデルのパネルがフェールするまで書き直す敵対的マルチエージェントフレームワークであるAgentGANで構築する。 その結果、2,114個の厳格化ステートメントを手作業で検証した人間の解法が得られた。
• 参考スコア（独自算出の注目度）: 1.1689657956099038
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Many NP-complete (NPC) problems have a polynomial-time (P) twin that differs in a single structural detail, such as 3- versus 2-colouring a graph. A model that reasons rather than recalls should notice which side of this boundary a problem falls on, yet existing benchmarks either fix the wording of each task or ignore its complexity class, so they cannot separate the two. We introduce P2NPCBench, a benchmark of 12 problem families in which every NPC problem is paired with a P twin posed over the same surface. To remove the textbook cues that enable recall, we build it with AgentGAN, an adversarial multi-agent framework in which a generator rewrites each statement until a panel of frozen code models fails, while an executable validity gate keeps every rewrite answer- and class-preserving. The result is 2,114 hardened statements with hand-verified reference human solvers. Evaluating 12 proprietary and open-source models, we find that every model scores lower on NPC statements than on their P twins (35.4% vs. 63.8% pass@1), and that 95.1% of model-family pairs fail more often on the NPC side. A tenfold time limit raises NPC accuracy only from 28.5% to 31.9%, so failures stem from wrong or crashing programs rather than slow ones. Hardening also narrows the class gap from 24.8 to 14.6 points, showing that part of the apparent gap reflects familiarity with textbook phrasing rather than complexity class.
• Abstract（参考訳）: 多くのNP完全(NPC)問題は多項式時間(P)双対を持ち、グラフの3色と2色のような1つの構造的な細部が異なる。 しかし既存のベンチマークでは各タスクのワードを修正するか、複雑性クラスを無視しているため、2つを分離することはできない。 P2NPCBenchは、各NPC問題とP双対を同一表面上でペアリングする12の問題系列のベンチマークである。 我々は、リコールを可能にする教科書の手がかりを取り除くために、AgentGANという逆のマルチエージェントフレームワークを使って、ジェネレータが各ステートメントをフリーズコードモデルのパネルがフェールするまで書き直す。 その結果、2,114個の厳格化ステートメントを手作業で検証した人間の解法が得られた。 12のプロプライエタリモデルとオープンソースモデルを評価すると、すべてのモデルがPツインよりもNPCステートメントの方が低い(35.4%対63.8%のpass@1)こと、モデルファミリーペアの95.1%がNPC側で失敗することが多いことが分かる。 10倍の時間制限により、NPCの精度は28.5%から31.9%にしか上昇しないため、失敗は遅いプログラムではなく、間違ったプログラムやクラッシュプログラムから生じる。 ハードニングはまた、クラスギャップを24.8点から14.6点に制限し、明らかなギャップの一部は、複雑性クラスよりも教科書のフレーズに精通していることを示している。

関連論文リスト

• Solving Every Step Is Not Enough: Milestone Oracles Reveal a Composition Gap in LLM Math Reasoning [5.227943373419647]
  大規模言語モデル(LLM)は、多段階数学問題の中間ステップを自分自身で解くことができ、ステップのロードマップと全ての答えが与えられたとしても、完全な問題に失敗する。 OracleLadder は LLM の数学推論が失敗する場所を特定するための診断評価手法である。
  論文  参考訳（メタデータ） (2026-09-26T04:51:33Z)
• SwiftSolve: A Self-Iterative, Complexity-Aware Multi-Agent Framework for Competitive Programming [4.611794255231338]
  我々は、複雑性を意識した競合プログラミングのためのマルチエージェントシステムSwiftを提案する。 プロファイリングと複雑誘導型リプランニングは精度を保ちながら非効率性を低下させることを示す。
  論文  参考訳（メタデータ） (2025-10-26T11:05:27Z)
• BeyondBench: Benchmark-Free Evaluation of Reasoning in Language Models [13.380359214677176]
  インターネット規模のトレーニングデータから汚染を避けるための評価フレームワークであるBeyondBenchを紹介する。 本フレームワークでは,44のアルゴリズムタスクを117のバリエーションでカバーし,3つの難易度に分類する。 85のオープンソースモデルと16のクローズドソースモデルを含む101の言語モデルを評価する。
  論文  参考訳（メタデータ） (2025-09-29T02:49:01Z)
• Eigen-1: Adaptive Multi-Agent Refinement with Monitor-Based RAG for Scientific Reasoning [53.45095336430027]
  暗黙的な検索と構造化された協調を組み合わせた統合フレームワークを開発する。 Humanity's Last Exam (HLE) Bio/Chem Goldでは,48.3%の精度を実現している。 SuperGPQAとTRQAの結果はドメイン間の堅牢性を確認した。
  論文  参考訳（メタデータ） (2025-09-25T14:05:55Z)
• Abduct, Act, Predict: Scaffolding Causal Inference for Automated Failure Attribution in Multi-Agent Systems [20.846301581161978]
  マルチエージェントシステムにおける障害帰属は、批判的だが未解決の課題である。 現在の手法では、これを長い会話ログ上のパターン認識タスクとして扱う。 A2P Scaffoldingは、パターン認識から構造化因果推論タスクへの障害帰属を変換する。
  論文  参考訳（メタデータ） (2025-09-12T16:51:15Z)
• ProcessBench: Identifying Process Errors in Mathematical Reasoning [62.80402845414901]
  本稿では,数学的推論における誤ったステップを識別する能力を測定するためのProcessBenchを紹介する。 ProcessBenchは3400のテストケースで構成され、主に競合とオリンピアードレベルの数学問題に焦点を当てている。 我々はProcessBenchについて、プロセス報酬モデル(PRM)と批判モデルという2種類のモデルを含む広範囲な評価を行う。
  論文  参考訳（メタデータ） (2024-12-09T15:11:40Z)
• Achieving >97% on GSM8K: Deeply Understanding the Problems Makes LLMs Better Solvers for Math Word Problems [50.76385564061713]
  CoT(Chain-of-Thought)のプロンプトにより、さまざまな推論タスクにわたるLLM(Large Language Models)のパフォーマンスが向上した。 CoTは通常、セマンティックな誤解エラー、計算エラー、ステップミスという3つの落とし穴に悩まされる。 意味的誤解の誤りに対処し,LLMの数学的問題解決能力を改善するために,DUP(Deeply Understanding the Problems)を提案する。
  論文  参考訳（メタデータ） (2024-04-23T12:16:05Z)
• DCR: Divide-and-Conquer Reasoning for Multi-choice Question Answering with LLMs [9.561022942046279]
  大規模言語モデル(LLM)の推論能力を高めるため,DCR(Divide and Conquer Reasoning)を提案する。 まず、信頼性スコア(mathcalCS$)に基づいて質問を2つのサブセットに分類する。 特に,質問を信頼性スコア(mathcalCS$)に基づいて2つのサブセットに分類する。
  論文  参考訳（メタデータ） (2024-01-10T14:38:46Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。