← Back to all news
arXiv Computation and Language By Nurul Labib Sayeedi, Md. Faiyaz Abdullah Sayeedi, Zabir Al Nazi, Mahbub E Sobhani, Shubhashis Roy Dipta

Did the Problem Actually Get Harder? Testing LLMs on Paired P and NP-Complete Problems Hardened by Adversarial Multi-Agent Rewriting

Read the original on arXiv Computation and Language →

The paper introduces P2NPCBench, a benchmark that pairs 12 NP‑complete problems with their polynomial‑time counterparts, using an adversarial multi‑agent system (AgentGAN) to rewrite problem statements until standard code models fail while preserving correctness and complexity class. The benchmark yields 2,114 hardened statements with verified human solutions, and evaluation shows that all tested models perform significantly worse on the NP‑complete versions (35.4% vs. 63.8% pass@1), with most failures due to incorrect or crashing programs rather than timeouts. The hardening process also reduces the performance gap between P and NP‑complete problems, indicating that prior gaps were partly due to familiarity with textbook phrasing.

Machine-generated by The Flow from the publisher's headline and feed description — not written or checked by a human. The full article lives at arXiv Computation and Language.

Related stories

arXiv AI
Oct 9

Code Understanding is a Bottleneck for Coding Agents

The paper introduces CABRA, a synthetic benchmark that constructs coding tasks from scratch using call‑graph transformations and scales difficulty along four axes: function traversal, search, runtime resolution, and instruction following. Experiments with eight large language models and six coding agents on 6,840 CABRA tasks show that while LLM accuracy degrades with task size, agents maintain high performance by leveraging tools; larger tasks trigger more tool calls, and a separate study on SWE‑bench verifies that tool‑call counts better predict agent accuracy than lines of code edited. The authors argue that CABRA exposes weaknesses in LLMs that are hidden by tool use and highlights the importance of code‑understanding abilities beyond mere editing. whyItMatters":"The study demonstrates that coding agents’ performance is more dependent on code‑understanding than on the amount of code edited, revealing a critical bottleneck for current coding agents."

By Nishant Balepur, Kiran Tomlinson, Tobias Schnabel
llmsagentsbenchmarks
More like this →
arXiv Machine Learning
Jul 14

EvoClawBench: Can Agents Learn Reusable Skills from Their Own Runs?

arXiv:2607. 09711v1 Announce Type: new Abstract: Existing agent benchmarks primarily test task completion, tool use, or skill utility, but do not isolate whether a runtime can convert evidence from its own runs into reusable skills that improve fresh executions after authoring overhead.

By Zhiyuan Peng, Xin Yin, Chenhao Ying, Zhe Cui, Zixiang Ding, Zhenhua Liu, Jiang Wu, Yuan Luo
llmsagentsnlpbenchmarks
More like this →