# Nondeterministic Polynomial-time Problem Challenge: An Ever-Scaling Reasoning Benchmark for LLMs

arXiv: https://arxiv.org/abs/2504.11239 · HTML: https://mlsanity.com/paper/2504.11239/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Placed in Reasoning benchmarks and evaluation, one of 17 directions in LLM reasoning.
- Builds on 9 of its 42 references that are in the map.
- First posted on arXiv 15 Apr 2025.

## Placed in

- LLM reasoning / [Reasoning benchmarks and evaluation](https://mlsanity.com/lr/reasoning-benchmarks-and-evaluation/)

## Builds on (most cited first, 9 of 9)

- [GPT-4 Technical Report](https://mlsanity.com/paper/2303.08774/) (2023)
- [Training Verifiers to Solve Math Word Problems](https://mlsanity.com/paper/2110.14168/) (2021)
- [ZebraLogic: On the Scaling Limits of LLMs for Logical Reasoning](https://mlsanity.com/paper/2502.01100/) (2025)
- [Benchmark Data Contamination of Large Language Models: A Survey](https://mlsanity.com/paper/2406.04244/) (2024)
- [On the Measure of Intelligence](https://mlsanity.com/paper/1911.01547/) (2019)
- [SuperGPQA: Scaling LLM Evaluation across 285 Graduate Disciplines](https://mlsanity.com/paper/2502.14739/) (2025)
- [Inference-Time Scaling for Complex Tasks: Where We Stand and What Lies Ahead](https://mlsanity.com/paper/2504.00294/) (2025)
- [Inference-Time Computations for LLM Reasoning and Planning: A Benchmark and Insights](https://mlsanity.com/paper/2502.12521/) (2025)
- [Can Large Language Models Reason? A Characterization via 3-SAT](https://mlsanity.com/paper/2408.07215/) (2024)

## Built on by (most cited first, 7 of 7)

- [NP-Engine: Empowering Optimization Reasoning in Large Language Models with Verifiable Synthetic NP Problems](https://mlsanity.com/paper/2510.16476/) (2025)
- [BeyondBench: Contamination-Resistant Evaluation of Reasoning in Language Models](https://mlsanity.com/paper/2509.24210/) (2025)
- [RedAHD: Reduction-Based End-to-End Automatic Heuristic Design with Large Language Models](https://mlsanity.com/paper/2505.20242/) (2025)
- [Rethinking the Unsolvable: When In-Context Search Meets Test-Time Scaling](https://mlsanity.com/paper/2505.22290/) (2025)
- [From Pixels to Digital Agents: An Empirical Study on the Taxonomy and Technological Trends of Reinforcement Learning Environments](https://mlsanity.com/paper/2603.23964/) (2026)
- [MathConstraint: Automated Generation of Verified Combinatorial Reasoning Instances for LLMs](https://mlsanity.com/paper/2605.08498/) (2026)
- [Reinforcement Learning without Ground-Truth Solutions can Improve LLMs](https://mlsanity.com/paper/2606.27369/) (2026)

## Abstract (arXiv)

Reasoning is the fundamental capability of large language models (LLMs). Due to the rapid progress of LLMs, there are two main issues of current benchmarks: i) these benchmarks can be crushed in a short time (less than 1 year), and ii) these benchmarks may be easily hacked. To handle these issues, we propose the ever-scalingness for building the benchmarks which are scaling over complexity against crushing, instance against hacking and exploitation, oversight for easy verification, and coverage for real-world relevance. This paper presents Nondeterministic Polynomial-time Problem Challenge (NPPC), an ever-scaling reasoning benchmark for LLMs. Specifically, the NPPC has three main modules: i) npgym, which provides a unified interface of 25 well-known NP-complete problems and can generate any number of instances with any levels of complexities, ii) npsolver, which provides a unified interface to evaluate the problem instances with both online and offline models via APIs and local deployments, respectively, and iii) npeval, which provides the comprehensive and ready-to-use tools to analyze the performances of LLMs over different problems, the number of tokens, the reasoning errors and the solution errors. Extensive experiments over widely-used LLMs demonstrate: i) NPPC can successfully decrease the performances of advanced LLMs to below 10%, demonstrating that NPPC is not crushed by current models, ii) DeepSeek-R1, Claude-3.7-Sonnet, and o1/o3-mini are the most powerful LLMs, and iii) the numbers of tokens in the advanced LLMs, e.g., Claude-3.7-Sonnet and DeepSeek-R1, are observed first to increase and then decrease when the problem instances become more and more difficult. Through continuously scaling analysis, NPPC can provide critical insights into the limits of LLMs' reasoning capabilities, exposing fundamental limitations and suggesting future directions for further improvements.