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

Imagine you're developing an AI that needs to solve complex problems, like figuring out the best way to color a graph. The challenge is that many problems are NP-complete, meaning they can be very hard to solve, while others have easier polynomial-time counterparts. Current benchmarks often present these problems in a fixed way, which can lead to models simply recalling answers rather than genuinely reasoning through the problem. This is what's called a lack of complexity awareness, where models struggle to differentiate between the two types of problems due to familiar phrasing or cues.

To address this, the authors created P2NPCBench, a benchmark that pairs NP-complete problems with their polynomial-time twins, ensuring that the phrasing is challenging enough to prevent simple recall. They used an adversarial framework called AgentGAN to generate 2,114 unique problem statements that maintain the integrity of the problem while removing textbook cues. The results showed that models performed significantly worse on NP-complete problems compared to their polynomial-time counterparts, highlighting the need for better reasoning capabilities in AI. This benchmark not only provides a more accurate assessment of model performance but also emphasizes the importance of understanding problem complexity in AI development.

The introduction of a benchmark that pairs NP-complete problems with polynomial-time twins is a significant advancement in evaluating reasoning capabilities.

The methodology includes rigorous validation of problem statements and comprehensive evaluation across multiple models, ensuring solid reliability.