Did the Problem Actually Get Harder? Testing LLMs on Paired P and NP-Complete Problems Hardened by Adversarial Multi-Agent Rewriting
Paper recorded by Signals 4 on 2026-10-21 in cs.CL. Abstract reproduced from arXiv; link to the original below.
Published 2026-10-21 on arXiv · recorded by Signals 4 on 2026-10-22
Category: cs.CL · 自然语言处理 · first seen 2026-10-22
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,
Read on arXiv →
Cite this page: Did the Problem Actually Get Harder? Testing LLMs on Paired P and NP-Complete Problems Hardened by Adversarial Multi-Agent Rewriting: the #178 most recent of 660 cs.CL papers we have recorded (as of 2026-10-21). Source: Signals 4 (Signals API) — https://data.jiangzhang.ca/signals4/t/papers/did-the-problem-actually-get-harder-testing-llms-on-paired-p-and-np-complete-pro.html
Free to quote with attribution to “Signals 4 (Signals API)”. Machine-readable:
papers.json
Get 4 AI signals a day by email — free.
Get 4 AI signals a day by email — free