Nondeterministic Polynomial-time Problem Challenge: An Ever-Scaling Reasoning Benchmark for LLMs
Authors: Chang Yang
Ruiyu Wang
Junzhe Jiang
Qi Jiang
Qinggang Zhang
Yanchen Deng
Shuxin Li
Shuyue Hu
Bo Li
Florian T. Pokorny
Xiao Huang
Xinrun Wang
Venue: Accepted by TMLR ()

Abstract: 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, instance, oversight and coverage. 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 aha moments, 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, where DeepSeek-R1 can outperform Claude-3.7-Sonnet and o1/o3-mini in most NP-complete problems considered, and iii) the numbers of tokens, aha moments 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 LLMs' reasoning capabilities, exposing fundamental limitations and suggesting future directions for further improvements.

Published in Transactions on Machine Learning Research (02/2026)
Nondeterministic Polynomial-time Problem Challenge: An Ever-Scaling Reasoning Benchmark for LLMs
Chang Yang",, Ruiyu Wang"*, Junzhe Jiang', Qi Jiang', Qinggang Zhang', Yanchen Deng', Shuxin Lit, Shuyue Hu', Bo Li', Florian T. Pokorny?, Xiao Huang', Xinrun Wang
The Hong Kong Polytechnic University, *KTH Royal Institute of Technology, 3 *Carnegie Mellon University, Naayang Technologioal Universily, à "Shanghai Artificial Intellgencce Laboratory, "Singopore Management University
chang- cwnpg@@ooonec.poopp... ruigwwokth.sse, zrwang www...eu.uu.....
Reviewed OpenReview: https: openreview. net/ pet/forum? id= xdd6566566
Abstract
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 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 casy verification, and coverage for real-world relevance. This paper presents Nondeterministic Polynomial-tine 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 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 uidely-used
tokens, the reasoning errors and the solution errors. Extensive experiments LLMs demonstrate: i) NPPC can succossfully decrease the performances of advanced LLMs to below 10%, demonstrating that NPPC is not crushed by current models, ii) DeepSeek-R1, Claude-3.7-Sonne and 11/3-mmint are the most powerful LLMs, where DeepSeek- R1 can outperform Souude-3.7-Sonnee and ol ol/o-mmini in most NP-complete problems considered, and fii) the numbers of tokens in the advanced LLMs, c.g., Claudo-3.7-Somnet and DeepSeck- 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 capabilitics, exposing fundamental limitations and suggesting future directions for further improvements.
1 Introduction
The remarkable successes of Large Language Models (LLMs) (Achiam et al., 2023) have catalyzed the fundamental shift of artificial intelligence. Recent breakthroughs on reasoning (Guo et al., 2025) enable LLMs to complete complex lasks, e.g.; math proof, code generation and computer use, which require the capabilities of understanding, generation and long-term planning. Various benchmarks, e-g., GPQA (Rein et al., 2024), AIME, SWE-bench (Jimenez et al., 2024) and ARC-AGI (Chollet, 2019), are proposed to evaluate these advanced reasoning capabilitics, where most benchmarks are curated and verified by human rescarchers with a finite number of questions. These benchmarks guide the directions for advancing LLM capabilities.
"Equal contribution
1 "Corresponding author

---

Published in Transactions on Machine Learning Research (02/2026)
Current benchmarks face two fundamental challenges that limit. their effectiveness for LLM evaluation. First, current benchmarks can be crushed in a short time: GSM8K (Cobbe et al., 2021) performance increased from approximately 35% to 95% within three years, while SWE-bench (Jimenez et al., 2024) scores improved from 7.0% to 64.6% merely eight months, as illustrated in Figure This rapid saturation sug- gests that these benchmarks quickly lose their discriminative power as models advance. Second, current benchmarks can be easily hacked or exploited. Static benchmarks are suscep- tible to data contamination and memorization issues, leading to overfitting rather than genuine capability assessment (Wu et al., 2025; Xu et al., 2024). While live benchmarks such as LiveCodeBench (Jain et al., 2025) address contamination by continuously introducing new problems, they require substantial ongoing human curation efforts. Similarly, human evaluation platforms like ChatbotArena (Chiang et al., 2024) incur significant costs (approximately $3,000 per evaluation) and remain vulnerable to strategic manipulation where MixEval (Ni et al., 2024) can achieve comparable correlation with human judgment at under $1 per evaluation. These limitations represent significant. obstacles for reliable evaluation of the rapidly evolved LLMs.
100
80
Performancs
60
20
OPGA
ARC-AGI
2023
2024
2025
Figure 1: Crush of benchmarks
To address these issues, we propose the ever-scalingness with four desiderata for a benchmark (as shown in Figure 2): i) scaling over complerily the benchmark can generate the problems with continually increasing complexities to avoid the crushing of the benchmarks. This ensures that as LLMs improve, the benchmark remains challenging by providing harder problems that push the boundaries of current capabilities for long-term diffcrentiation. ii) scaling over instance the benchmark can generate an infinite number of instances to avoid the exploitation and overfitting. This prevents LLMs from memorizing specific problem instances during training and ensures that the evaluation truly measures the reasoning capabilities of LLMs. ili) scaling over oversight - the benchmark can verify the correctness of the solutions efficiently for the problems with any complexity. This is crucial because as problem complexity increases, manual verification becomes impractical or impossible. Automated and reliable verification enables evaluation at scale and ensures that harder problems can be verified efficiently, making the benchmark practically sustainable. iv) scaling over coverage the benchmark should comprehensively cover problem types that are highly relevant to real-world applications, rather than focusing puzzles. rare edge cases. This ensures that performance improvements the benchmark translate to practical value, measuring capabilities that matter for downstream tasks and roal-world deployment rather than narrow, specialized skills. These four desiderata for ever-scalingness ensure continuous differentiation among LLMs over extended periods, identifying fundamental limitations for further improvement.
Complexity
Instances
Ever-
Scalingness
Oversight
Coverage
Figure 2: Desiderate of ever-scalingness
To construct the ever-scaling benchmark, we focus on nondeterministic polynomial-time (NP) problems whose solutions can be verified in polynomial time (Cormen et al., 2022). Specifically, we larget on NP-complete (NPC) problems, i.e., the most computationally challenging problems in the NP class, for three key reasons. First, NPC problem instances can be systematically generated across arbitrary difficulty levels through controlled parameters, e.g., numbers of variables, enabling precise scaling of both complexity and instance. Second, NPC problems are intrinsically "difficult to solve, easy to verify" i.e., no polynomial-time algorithms have been discovered for solving NPC problems, making them computationally intractable even with specialized tools, while their solutions remain efficiently verifiable. Problems in the complexity class can be solved in polynomial time. When LLMs are equipped with code execution capabilities, they can generate and execute algorithms to solve these problems directly. Therefore, such benchmarks become susceptible to trivial solutions through computational tools rather than genuine reasoning. Conversely, NP-hard problems, particularly those lacking polynomial-time verification procedures, present the challenge for verifying the solutions for large-scale problem instances. Third, NPC problems demonstrate broad applicability, including
2

---

Published in Transactions on Machine Learning Research (02/2026)
diverse real-world scenarios (e.g., routing (Toth & Vigo, 2002) and protein folding (Crescenzi et al., 1998)) and various puzzles, e.g., Sudoku (Seely et al., 2025). The theoretical foundation for using NPC problems as a comprehensive evaluation framework stems from the fundamental property that any NP problem can be reduced to an NPC problem in polynomial time, establishing NPC problems as a thcorctically grounded, universal framework for computational problem-solving assessment. Therefore, NPC problems are the foundation problems of all computational problems and LLMs are the foundation models for wide range tasks, thus leading to our ever-scaling uondeterministic polynomial-ting problem challenge (NPPC) (Figure 4(a)).
Specifically, NPPC has three main modules: i) npgym, which provides a unified interface of 25 well-known NPC problems and can generate any number of instances with any levels of complexitics, which implics the ever-scalingness of NPPC, ii) npsoloer, which provides a unified interface to evaluate the problem instances with both online and offline models via APIs and local deployments, respectively, to facilitate users to evaluate their own models and iii) npeval, which provides comprehensive and ready-to-use tools to analyze the performances of LLMs over different problems, the number of tokens, the "aha moments", the reasoning errors and the solution errors, which can provide in-depth analysis of the LLMs and the insights to further improve the LLMs' reasoning capabilities. Extensive experiments over widely-used LLMs, ie.. GP'T-4o-mini GPT-4o, Soaude-3.7-Sonncee DeepSeck- V3, DeepSeck-R1, and OpenAI ol-mini, demonstrate: i) NPPC can successfully decrease the performances of advanced LLMs to below 10%, demonstrating that NPPC is not crushed by current LLMss, ii) DeepSeek-R1, LLMs, where DeepSeek-R1 can outperform Sroude-3.7-Sonnce and ol-mini in most NP-complete problems considered, and iii) the numbers of tokens in the advanced LLMs, e.g.. -laude-3.7-Somnt and DeepSeek- R11, are observed to first increase and then decrease when the problem instances become more and more difficult. We also analyze the typical reasoning crrors in the LLMs, which provide the insights of the fundamental limitations of current LLMs and suggest the potential directions for further improvement. To the best of our knowledge, NPPC is the first ever-scaling benchmark for reliable and rigorous evaluation of the reasoning limits of LLMs, according to the four desiderata defined previously.
Salaudee..7-Sommee and ol /o3-mini are the most powerful
2 Related Work
Traditional benchmarks are typically curated by hu- man with static datasets. Abstraction and Reasoning Corpus (ARC-AGI)-1 (Chollet, 2019) is designed to be "casy for humans, hard for AI", which is formed by hunan-curated 800 puzzle-like tasks, designed as grid-based visual reasoning problems. o3 at high compute scored 87% on ARC-AGI-1 (OpenAI, 2025), which roughly crushes the ARC-AGI-1 benchmarks and leads to the emergence of the ARC-AGI-2 bench- mark. This pattern exemplifies a fundamental chal- lenge with traditional benchmarks for LLMs, includ- ing MMLU (Hendrycks et al., 2021), GPQA (Rein
Table 1: Comparison of different reasoning benchmarks
according to the ever-scalingness.
Complexity
Instanco
Ovanaight
Coverage
NPHaddEad (Pan Al., 2024)
Zeboo (Linn et al., 2025)
Reasoning Gym (Stojunovaki et al., 2025)
Sudokn Beuth (Sedly al., 2025)
ARC-AGI-1 2 (Chollet, 2019)
NPPC (this work)
et al., 2024), GSM8K (Cobbe et al., 2021), ), and SWE-bench (Jimenez et al., 2024), where static benchmarks are systematically solved within relatively short periods (as shown in Figure 1). Therefore, researchers have to continuously either develop new benchmarks, e.g., MMLU-Pro (Wang et al., 2024b) and SuperGPQA (Du et al., 2025), or regularly update with new datasets and problems, e.g., LiveCodeBench (Jain et al., 2025) and SWE-bench-Live (Zhang et al., 2025). However, these remodics rely on extensive human efforts to maintain their relevance and difficulty and cannot fully address the crushing issue of benchmarks.
Several recent benchmarks consider either NP(C)) problems, e.g., 3SAT (Balachandran et al., 2025; Hazra et al., 2024; Parashar et al., 2025), or partially the vver-salingness (Fan et al., 2024; Stojanovski et al., 2025) (displayed in Table 1). NPHardEval (Fan et al., 2024) considers 3 problems from P, NPC and NP-hard classes and use these class to evaluate the LLMs, We note that the problems in P class can be solved by augmenting the LLMs with tools, c.g., code rumning, and the NP-hard problems cannot be verified efficiently, therefore, NPHardEval cannot scale over the scalable oversight. Only 3 NPC problems are considered, i.c., Knapsack, Traveling salesman problem (TSP) and graph coloring, and the instances of each problem in NPHardEval are
3

---

Published in Transactions on Machine Learning Research (02/2026)
finite and only regularly updated, which cannot scale over the instance and complexity. ZebraLogic (Lin et al., 2025) considers one logic puzze, i.e, Zebra puzzle, to test the reasoning capabilities of LMs when the problems' complexities increase. However, the reasoning capability on specific puzzles does not necessarily transfer to other problems, which violates the scaling of the coverage. Sudoku-Bende (Seely ct al., 2025) locuses on one specifie Sudoku game with 2765 procedurally generated instances with various difficulty levels. Reasoning Gym (Stojanovski et al., 2025) an ongoing project which collects the procodural generators and algorithmic verifiers for infinite training data with adjustable complexity. Though with some NP(C) problems, e.g., Zebra puzzles and Sudoku, the reasoning gym does not specifically focus NPC problems and cannot meet the desiderata of ever-scalingness. Several recent work leverages NP(C) problems as the training environments to improve the general reasoning capabilities of LLMs (Zeng et al., 2025; Li et al., 2025; Liu el al., 2025a), which demonstrates the advantages of NP(C) problems in terms of controllable difficulty and efficient solution verification. These existing efforts highlight the need for a systematic approach for training and benchmarking LLMs grounded in the complexity theory. This motivates the formulation of ever-scalingness and the development of NPPC.
3 Preliminaries
P and NP Problems. The problems in P class are decision problems that can be solved in polynomial time by a deterministic Turing machine, which implics there exists an algorithm that can find a solution in time proportional to a polynomial function, e.g., O(r²), of the input size n. Examples include sorting, shortest path problems, and determining if a number is prime. The problems NP class are decision problems that can be solved in polynomial time by rondetermémistic Turing machine, where a proposed solution can be easily verified, though finding that solution might require more time (as displayed in Definition 1). All P problems are also in NP, but the reverse remains an open question, known as "P vs. NP problem". NP problems form the cornerstone of computational complexity theory, for which solution verification is tractable (polynomial time) even though solution discovery may be intractable (potentially exponential time), i.e., "difficult to solve, easy to verify". Many real-world optimization problems can be formulated as NP problems, such equilibrium finding in game theory, portfolio management, network design and machine learning.
NP-hard
NP-complete
NP
P
Figure 3: Complexity classes
Definition 1 (NP Problems). The complexity class NP consists of all decision problems Ω such that for any "yes" instance I of Ω there exists a certificate a of polynomial length in [Z] where a deterministic Turing machine can verify in polynomial time that e is a valid certificate for I.
NP-complete (NPC) Problems. Formally, a problem Q is an NPC problem if the problem is in NP, and ii) any NP problems can be transformed to problem Q in polynomial time. This reducibility property establishes NPC problems the "hardest" problems in NP class. The Cook-Levin theorem established SAT as the first proven NPC problem (Cook, 2023; Karp, 2009), while 3SAT is the special case of SAT and is also an NPC problem. Subsequent NPC problems typically proven via reduction chains back to 3SAT or other established NPC problems. The most well-known NPC problems include vertex cover problem, clique problem, traveling salesman proble (TSP), Hamiltonian path/cycle problem, etc. NPC problems play the most important roles in answering the "P vs. NP problem", i.e., any NPC problem were shown to have a polynomial algorithm, then P NP. However, despite docades of rescarch, no polynomial-time algorithms for any NPC problem is discovered, which implies that NPC problems are compulationally intractable by current methods. While NP-hard problems represent broader class that includes optimization variants and potentially harder problems, they are less suitable for benchmarks because their solutions cannot be verified in polynomial time, which fundamentally limits the scaling of complexity and oversight of the benchmarks.
Reasoning in LLMs. The reasoning ability of LLMs refers to the model's capacity to tackle complex problems, c.g., mathematical proof, code generation through multi-step thinking and context understanding. Recently, specialized reasoning models have been proposed. OpenAI-ol is an LLM trained with reinforcement learning (RI.), which enables the model to perform complex reasoning, including logical thinking and problem
4

---

Published in Transactions on Machine Learning Research (02/2026)
(a)
(c)
nygym
Foundation Models
NPPC
Foundation Problems
configs
(true, false)
performance
generator
verifier
Accuracy vs. Difficulty
(b)
H
tokens
Token number Difficulty
npgym
instance
solution
NPPC
errors
1.Proflem-specific errors 2. 2.Typical reasoning Failures
A
LLM
parsing
template
npsolver
npeval
prompt template
leaderboard
npsolver
npeval
Figure 4: Overview of NPPC. (a) NPPC represents the intersoction of foundation models and foundation problems. (b) The three main components of NPPC: npgym (problem generation), npsolver (solution generation), and npecal (evaluation).
(c) Workflow diagram: npgym configuring generators and verifiers, npsolver using LLMs to generate solutions, and npenal mcasuring performance metrics.
solving, via chain-of- thought (CoT). ol thinks before it answers and can significantly outperform GPTT4o on reasoning-heavy tasks with high data efficiency. DeepSeek-R1 (Guo et al., 2025) is an enhanced reasoning model designed to improve LLMs' reasoning performance that incorporates multi-stage training and cold-start data before the large-scale RT. DeepSeek-RI demonstrates remarkable reasoning capabilities, and achieves comparable performance OpenAl-ol across various reasoning tasks, e.g., mathematical problems, code generation, and scientific reasoning. Additionally, there are open-sourced medium-sized LLMs with strong reasoning capabilities, e.g., De-3Se distilled version of DeepSeek- -R, and QwQ-32B.
4 Nondeterministic Polynomial-time Problem Challenge
We introduce Nondeterministic Polynomial Problem Challenge (NPPC), an ever-scaling reasoning benchmark for LLMs. There are three main components in NPPC (as displayed in Figure 4(b)): i) npgym, which provides unified interface of well-known NPC problems and can generate any number of instances and verify the solution 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, to facilitate the users to evaluate their own models and iii) npeval, which provides the comprehensive and ready-to-us use tools to analyze the performances of LLMs over problems, the number of tokens, the "aha moments", the reasoning and solution errors, providing the in-depth analysis the LLMs' reasoning capabilities.
4.1 Problem Suite: npgym
Interaction Protocol. Typically, NPC problems are the decision problems where given the instance I, the answer is "Yes" or "No". However, the LLMs may take random guess without reasoning for the true solution (Fan et al., 2024). Therefore, consider more challenging setting: given the instance I, the LLM needs to generate the solution for the instance. This setting will enforce the LLMs to reason for the correct solutions and the NPPC needs to provide the cortificate o to verify the solutions generated by the LLMs. apgym provides a unilied interface of NPC problems to interact with LLMs. The interaction between пpgym and the LLM is displayed in Figure 4(c). npgym generates the instance I with the given configuration, and the LLM reccives the instance and generate the solution s, then the solution verified by npgym with the output trree false). The representation of problem instances designed to be concise and complementary to include all necessary information for the I.I.Ms to reason for the solution.
5

---

Published in Transactions on Machine Learning Research (02/2026)
Core Problems and Extension. There are 25 typical NPC problems implemented in npgym. Among all NPC problems, 12 typically NPC problems are selected as the core problems, chosen for their fundamental importance and broad real-world applications across domains such as logisties and routing (TSP, Hamiltonian Cycle), network optimization (Vertex Cover, Graph 3- &.Colurrbilityy, resource allocation (Bin Packing, 3- Dimensional Matching), automated reasoning (3SAT), computational biology (Shortest Common Superstring), and mathematical optimization (Quadratic Diophantine Equations, Minimum Sum of Squares). The other 13 problems are categorized as the extension problems, covering specialized applications in social networks, facility location, cryptography, and data mining. A full list of the 25 problems is displayed in Table 2.
Table 2: Core Problems and Extension.
3-Satisfiability (3SAT), Vertex Cover, 3- Dimmessional Matching (3DM), Travelling Salesman (TSP), Hamiltonian Cycle, Graph 3-Colourability (3-COL), Bin Packing, Maximum Leaf Spanning Tree, Quadratie Diophantine Equations (QDE), Minimum Sum of Squares, Shortest Common Superstring, Bandwidth
Core
Clique, Independent Set, Dominating Set, Set Splitting, Set Packing, Exact Cover by 3-Sets (X3C), Minimum Cover, Partition, Subset Sum, Hitting String, Quadratic Congruences, Betweenness, Clustering
Extension
Generation and Verification. Specifically, for each problem, npgym implements two functions:
(iatte__istannee)> given the configurations, this function will generale the problem instances. Taking the 3SAT as an example, the configurations include the number of variables and the number of clauses. The generated instances are guarantcod to have at least one solution and not necessarily to have a unique solution, which is ensured by the generation process.
stt__ssoltoonnn) (+): given the solution and the problem instance, this function will verify whether the solution is correct not. Additional to the correctness, this function also returns the error reasons. Taking the TSP as an example, the errors include i) the solution is not tour, ii) the tour length exceeds the larget length. The full list of the errors is displayed in Table 7.
Difficulty Levels. NPC problems exhibit distinct combinatorial structures and computational characteristics. npgym implements the difficulty levels (Cobbe et al., 2020; Fan et al., 2024) establish a standardized metric for quantifying the computational complexity. Specifically, the difficult levels are determined with a two-stage approach: First, the parameters for NPC problems are manually configured based on problem-specific insights (e.g,, graph size, constraint density) by human experts. Second, to facilitate intuitive visualization and meaningful benchmarking comparisons, we empirically calibrate the difficulty scale using LLM performance data. This calibration serves purely as a post-hoc validation step to ensure the difficulty progression is interpretable for benchmark users, which does not influence problem generation or introduce circular reasoning into the evaluation hethodology. The calibration confirms that higher difficulty levels (as determined by theoretical complexity) correspond to lower LLM success rates, providing an intuitive scale where level problems achieve >90% success and level 10 problems achieve <10% success. The comprehensive justification of this approach is in Appendix A.6. Appendix C.1 includes full specifications of difficulyy levels.
Is There a Unified Principle for Difficulty Levels of NPC Problems? Establishing a unified principle for determining difficulty levels across all NPC problems is fundamentally challenging due to inherent differences from both theoretical and practical perspectives. From the problem perspective, the structural heterogeneity of NPC problems prevents the establishment of universal difficulty metric. While all NPC problems are polynomially reducible to each other in theory, they exhibit vastly different characteristics in practice. These differences include: i) representation complexity, i.e., problems vary in how constraints and variables are encoded (graph structures vs. logical formulas vs. numerical constraints), ii) Search space topology, i.c., some problems have smooth difficulty landscapes while others contain sharp complexity transitions. This heterogeneity means that uniform metrics such as simple parameter counts or roistraint numbers- fail to capture the true computational difficulty that emerges during actual problem-solving From the LLM perspective, LLMs demonstrate highly variable performance across different NPC problems, and the problem instances generated should not be too easy or too difficult, which may fail to differentiate the capabilities of LLMs. Additionally, there exists no established theoretical framework for determining the
6

---

Published in Transactions on Machine Learning Research (02/2026)
upper bounds of problem difficulty that LLMs can effectively handle, making difficulty calibration necessarily empirical and problem-specific, which justifies our two-stage approach to determine the difficulty levels.
Ever-scalingness of npgym. прoуm fulfills the four desiderata of ever-scalingness. Specifically, npgym can generate enormous problem instances with arbitrary difficulty levels, enabling scaling over complexity and instance continuously differentiate the LLMs while avoiding hacking, e.g,; memorization. The scalability is fundamentally grounded in the mathematical properties of NPC problems: for any fixed instance size n, the solution space grows exponentially. Solution verification in пpgym is computationally efficient, guaranteed by the inherent properties of NP problems where candidate solutions mpgymn supports extensible coverage through simple interface requiring only two core functions and difficulty specifications for adding new NP(C) problems and no specialized tool is required, enabling the benchmark to expand across diverse computational domains while maintaining consistency in evaluation methodology.
be verified in polynomial time.
4.2 Solver Suite: npsolver
Prompt Template. The prompt template for LLMs is designed to be simple without any problem- specific knowledge and consistent across all problems. Therefore, the prompt. template (displayed above) includes: i) problem description, which provides the concise definition of the NPC problem, including the problem name, the input and the question to be solved, ii) the context examples, where each example is formed by the instance and its corresponding so- lution, demonstrating the input and output patterns to help LLMs to generate the solution, iii) the target instance to solve, and iv) the general instruction about the solution formal, where the solution is re- quired to be in the JSON format for easy extracting and analyzing. We note that the structural output in JSON format may bring difficulties for LLMs to generate the correct solution, especially for offline models (analyzed in the experiments). More details are displayed in Appendix D.
appc_template
<problem_name> Problem Description:
sproblen_description Examples:
< sin_context_exapple
Problen to Solve:
Problem: <problen_to_solve
Instruction:
Now please solve the above problem. Reason step by step and present your the "solution" field in the following jaon format:
ere jeon {"solution"; "___"}
...
example,
@taaple_ad___ and_aandduullae
solution ""*Problem:
{"solution": <example_solution>>
Figure 5: Prompt Template of NPPC
To streamline response extraction across various LLMs,, we present npsolver, solver suite that provides unified interface for both online (API-based) and offline (locally deployed) models. npsolver includes: i) prompt generation, which constructs problem-specific prompts dynamically using the designed prompt templates, ii) LLM completion, that handles response generation via either online APIs supported through LiteLLM (BerriAI, 2023), or offline models via vLLM (Kwon et al., 2023); iii) solution extraction, which applies regular expressions to parse JSON-format responses, ensuring a consistent. validation pipeline across all models; iv) error reporting, that standardizes error messages. Through the unified interface, npsolver enables both online and offline models to share common workflow for completion.
Completion with LLMs.
4.3 Evaluation Suite: npeval
Comprchensive LLM evaluation across all problems and difficulty levels is computationally expensive due the randomness in instance generation and LLM responses?. While existing benchmarks evaluate LLMs on fixed datasets (e.g., 200 instances across difficulty levels in (Lin et al., 2025)), diffieulty-speeific performance assessment is required, thus leading to the development of npeeaal (as displayed in Figure 4(c)). Inspired by rliable (Agarwal et al., 2021), npeval aggregates performance across multiple independent seeds (typically 3) for each difficulty level, generating 30 instances per seed -the minimum sample size for statistical analysis. This sampling strategy enables statistically sound performance aggregation while controlling instanco-specific variance within budget constraints. npeval provides four performance measures following rliable, i.e., inter-
Randomizing responses, L.e, non-zero temperature, used better performance (Guo et al., 2025).
7

---

Published in Transactions on Machine Learning Research (02/2026)
QwQ-32B
GPT-4o-mini
Claude-3.7-Somee
DeepSeek-V3 -V3225033
o1 mini
DeepSeek-R1-328
GPT-4o
DeepSeek-V3
DeepSeek-R1
03-mini
3SAT
Vertex Cover
Superstring
QDE
1.0
Accuracy
0.8
0.4
0.0
2
5
7
10
4
9
1
5
6
8
10
2
4
5
7
10
3DM
TSP
Hamiltonian Cycle
Bin Packing
Accura 1
0.8
0.4
0.0
2
3
4
5
7
8
10
2
4
6
7
9
10
1
4
6
8
9
10
2
3
5
7
8
10
3-COL
Min Sum Square
Bandwidth
Max Leaf Span Tree
1.0
Accurapy
0.8
0.6
0.4
0.2
0.0
2
3
4
5
7
8
9
10
1
2
3
4
5 6
7
8
9
10
1
3
5
6
7
8
10
2
3
5
7
8
10
Figure 6: Performance over difficulty levels measured by 1QM
quantile mean (IQM), mean, median, and optimality gap, which employ stratified bootstrap confidence intervals (SBCIs) with stratified sampling for aggregate performance estimation, method suitable for small sample sizes and more robust than standard deviations. We note that IQM trims extreme values and computes the interquartile mean across runs and tasks to smooth out the randomness in responses, which highlights the consistency of the performance and complements metrics like mcan mcan/median /mddian to avoid outlier skew. The framework analyzes both prompt and completion tokens across problems and difficulty levels, as well as the number "aha moments" reasoning processes in (Guo et al., 2025). Additionally, it categorizes errors into solution errors (detected by npgym's verification) and reasoning errors (flaws in the LLM's internal problem-solving process). More details can be found in Appendix C.3.
5 Results
We conduct comprchensive experiments to evaluate the reasoning capabilities of statc-of-tho-art LLMs across the NPPC benchmark. Our evaluation encompasses representalive models, including two offline medium-sized reasoning models (QwQ-32B and DeepSock-R1-32BB) four online advanced non-reasoning models (GPT-4o-mini, GPT-4o, Claude-3.7-Sonnet, and versions of DeepSeek-V3), and four online reasoning-specializet models (DeepSeck-Ri ol-mini, and o3-mini). For each problem, generate instances across 10 difficulty levels, with each level designed to progressively challenge model capabilities through increased problem complexity. Following our rigorous sampling strategy, we evaluate each model on 90 instances per difficulty level (30 instances across 3 independent seeds) to ensure statistical reliability.
5.1 Analysis of Performance
The performance of considered LLMs over difficulty levels is displayed in Figure 6, where all models exhibit a decline in accuracy as difficulty levels increase across all 12 NPC problems. Take 3SAT as an example, all online models except for DeepSeek-BR R1 drop from 2 80% accuracy to close to 0% at the last level, and DeepSeck-R1 shows the slowest docline but still falls to < 15% accuracy. All models collapse around or even below 10% accuracy at extreme difficulty confirms that NPPC not crushed against the SoTA Superstring problem,
LLMs and discriminate their capabilities. One exception is

---

Published in Transactions on Machine Learning Research (02/2026)
35AT
Vertex Cover
Superstring
QDE
3DM
TSP
Distribution
Hamiltonian Cycle
Bin Packing
3-COL
Min Sum Square
Bandwioth
Max Leaf Span Tree
Distribution
1234567890 1234567899
123456789ID
12345678911
1234 9800
12345677
QwQ-328 DeepSeek-R1-328
GPT-4o-mini
Claude-3.7-Sonnet
Deepseek-V3-2503
e1-mini e3-mini
GPT-4o
DeepSeek-v3
DeepSeek-R1
Figure 7: Ranks of models over problems, where the x-axis represents the rank, ranging from to 10, as we evaluate 10 models, and the y-axis shows the distribution of different LLMs across the ranks.
where the accuracy is still above 50% even for the level 10, while other models all decreased into less than 20%, which demonstrates the superiority of Claudc-3.7-Somnct to deal with long contexts, where the prompts at level 10 is more than 50K?. All models perform similarly on the Bandwidth problem, which may be mainly due to the fact that none of the models are familiar with this specifie problem. Both 03-mini and DeepSeek- V3-2503 demonstrate superior performance to their predecessor models, ol-mini and DeepSeek- V3, respectively, validating continually improvements in both non-reasoning and reasoning LLMs.
IQM
Mean
Median
Optimality Gap
03-mini
ol-mini
DeepSeek-R1
DeepSeek-v3-2555
I
DeepSeek-V3
(laude-3.7-Sonme
GPT-40
GPT-4o-mini-
DeepSeek-R1-3e
QwQ-32B
0.2
0.4
0.6
0.15
0.30
0.45
0.60 0.00
0.25 0.50
0.75
0.45
0.60
0.75
Figure 8: Performance interval over all problems across all levels
The ranks of models problems are shown in Figure 7, which measures the models' performances across different levels of specific problem. We observe that DeepSeek-R1 and 03-mini demonstrate statistical dominance in achievement of first-rank positions among prasoning-specialiin Sonnet is the best non-rcasoning model compared with the two versions of DecpSeck-v3 and GPT-4o, even better than ol-mini. Figure visualizes the performance interval different LLMs over all problems across all difficulty levels, where all four aggregate metrics are employed measure LLMs' performance, We observe that DeepSeek-R1 achieves superior performance with the highest 1QM, mean, medium values and the lowest. optimality gap, followed by o3-mini and Claude-3.7-Somme while GPT-4o-miní performs in opposite way.
architectures and Claude-3.7 7-
Takeaways
NPPC can successfully decrease the performances of advanced LLMs to < 10%
DeepSeck- R1, o3-mini and Claude are the strongest LLMs across all considered NPC problems
The ranks of different LLMs depend the specific NPC problems
We do continually increase the difficulty this problem all other models worse than 10%.

---

Published in Transactions on Machine Learning Research (02/2026)
QwQ-328
DeepSeek-R1-328
GPT-4o-mini
GPT-4o
Claude-3.
3000
Completion
5000
5000
2000
1000
1000
1 5
910
2 3 4
910
12 4 5
910
2 4
8 910
1
4
910
V3
DeepSeekvV-2500 V3-2533
DeepSeek-RR
01-mini
03-mini
4000
4000
20000
Comoletion
20000
10000
2000
2000
10000
0
4
2
910
910
910
910
Figure The number of tokens of different models on 3SAT. The correct and incorrect solutions are represented blue and red points, respectively, and the line the average values over all instances.
5.2 Analysis Used Tokens
Figure displays the token utilization across models on 3SAT. Offline models (QwQ-32B, DeepSeck-R1-325, rapidly approach maximum token limits and incorrect solutions (red) usually take more tokens than correct solutions (blue). Among online models, DeepSeek-R1 R.1 demonstrates highest consumption (10,000-20, ,000 tokens) for successful solutions, while o-series models exhibit significant variance, with outliers exceeding 40,000 tokens at higher complexity levels. DeepSeek-RI and o3-mini show steeper token scaling compared to ol-mini and Claude-3.7-Sonnee, indicating advanced reasoning models leverage increased token allocation for complex wroblem-solvingg GPT-4o variants maintain relatively efficient token utilization (<2,000) across all complexitios. This quantifics the computational serrieccy-performnn tradeoff between specializod reasoning architectures and general-purpost models. Similar phenomenon moments (instances of insight during reasoning, marked by phrases like "wait") in the reasoning contents of DeepSeek-RIl Due to the limited space, full results of tokens over all problems and the analysis of aha moment are displayed in Appendices and J, respectively.
also observed in the analysis of the aha
Takeaways
Reasoning models solve more difficult problems by scaling up the number of tokens used
The number of tokens used first. increase then decrease, indicating the failure of LLM reasoning
5.3
Analysis of Solution Errors
QwQ-328
DeepSeek-R1-328
GPT-4o-mini
Taude-3.7-Sonnet
100
50
4 544566
90
2
666666 7 90
2 3
4 6
90
9
3
5 7
90
DeepSeek-V3
DeepSeek V3-2503
2503
DeepSeek-R3
ol-mini
03-mini
50
2
4
6
8
9
10
2
8 90
2
8
10
2
3
6
7
8
9
10
2
4
8 9188881
JSON ERROR
VERIFICATION ERROR
3SAT ERROR
3SAT ERROR 2
Figure 10: The number of errors of different models on 3SAT
The solution errors of 3SAT is displayed in Figure 10. The results show that the distribution of these errors varies across models and difficulty levels. As the difficulty increases, the frequency of certain error types tends to increase as well. For QwQ-32B, JSON ERROR dominate across all levels, which is mainly due to the reasoning process is not finished when the context reaches the limits (7500 Tokens). For other models (such as GPT-4o, Claude-3.7-Sonnet, and DeepSeek-R1), problem-specific errors (3SAT ERROR
TThe reasoning
mini not available analysis.
10

---

Published in Transactions on Machine Learning Research (02/2026)
and 2) become more prevalent at higher difficulty levels. Interestingly, we observe that some models (e.g., DeepSeek-R1-325 DeepSeek-V3. V3, GPT-40 and ol-mini) exhibit increasing JSON error at higher difficulty levels, similar to how humans might lose track of formatting instructions during lengthy reasoning processes on challenging problems. DeepSeek and GPT models show a more balanced distribution of error types. The o-series models demonstrate relatively better performance at intermediate difficulties but still encounter increasing problem-specific errors at the highest complexity levels. This error analysis provides valuable insights into not just whether models fail, but specifically how they fail when tackling increasingly complex NPC problems, which could inform future improvements to reasoning capabilities in LLMs.
Takeaways
Offline models, e.g., QwQ-32B, and DeepSeek- V series models suffer the format errors
The problem-specific solution errors provide the foedback for further improving the LLMs
.
5.4
Analysis of Reasoning Failure Cases
Table 3: Examples of Failure Cases for Deepseek-RI.
Failure Reason 1: Cascading Assumptions and Placcholder /Guess
At this point, I'm not sure. Given the time I've speut and the complexity, perhaps the solution is the string proojanylmaddspperdbb with length 20, even though some required substrings might be missing. But according to the prohlem statement, there is salution. So I'll have to take guess, But given the time I've spent and the need to provide an answer, I'll make an educated guess.
Failure Reason 2: Manual Computation Errors and Complexity Avoidance
So, if node an edge that's not covered by any other node, then node must in the vertex cover. But chorking that for each edge would be time-consuming. Let's look for edges that have unique node. For example, if there's an edge (a, b). and neither a nor are connected to any other nodes, then one of them must be in the cover. But in graph of 40 nodes, this unlikely. So probably most nodes have multiple edges.
Failure Reason 3: Reliance on Prompt Examples
Wait, in the example problem, the solution included nodes 0, 2, 4, 5, 6, 7, 8, 9, 13, 14, 15, 19, 20, 23, 25, 26, 30, 37. So maybe similar patterns here. But the new problem's 's edges the solution is similar to the example. The example's 's solution includes nodes 0, 2, 4, 5, 6, 7, 8, 9, 13, 14, 15, 19, 20, 23, 25, 26, 30, 32, 34, 37. Looking the problem's 's edge sct, perhaps some of these nodes are also high-dogree here. Let's see, Wait, another idea: the example solution included nodes 0, 2, 4, 5, 6, 7, 8, 9, 13, 14, 15, 19, 20, 23, 25, 26, 30, 32, 34, 37. If I look at these nodes, perhaps they are all the nodes from one aide a bipartition.
different.
Alternatively, perhaps
Fallure Reason 4: Reasoning Repetition
For example, node 8 appears in edges like (8,18), (8.35), (8,21), (8.30), (8,39), ctc. Maybe node 8 is hub. In the problem to solve, node 8 is involved in many edges, as per the edges provided. So including 8 in the cover would cover lot of edges. ... For example, node appears in of edges. Including node would cover many edges. For example, many edges involve node B. So including node 8 is must.
For Deepseek-R1, the reasoning content of the failure cases shows several reasons that lead to wrong answers. i) cascading assumptions and placeholder /gues::: DeepSeek- R1 begins with high-level approach but quickly resorts to making assumptions to derive answers without logical deduction and considering all the conditions, and finally returns a placeholder or an educated guess; ii) manual computation errors and complexity avoidance: DeepSeek-R1 uses inefficient manual calculations (prone to errors) instead of programming, skips complex steps even the reasoning correct, and resorts to guesses to avoid effort; iii) reliance on prompt examples: DeepScek-R1 relies heavily on the example solution, making it waste time and get distracted by verifying and editing the solution instead of solving the problem directly; iv) reasoning repetition: DeepSeek-RI gets stuck repeating the same logic without making further progress, wasting time and tokens. We list some typical examples of failure cases of DeepSeek-R1 in Table 3, and more examples are shown in Table 22 in Appendix L. Failure cases of Clande-3.7-Sonne typically exhibit more concise reasoning, as it often outlines a high-level step-by-step approach but omits detailed calculations and rigorous verification, and it relies on approximate calculations to derive a final answer, incorrectly asserting that the result has been validated. More examples are shown in Tables 23 and 24 in Appendix L.
5.5 Cost of Evaluations
According to the cost analysis in Table 4, we observe significant cost variations across different models when evaluated on the same benchmark tasks. With approximately 31 million prompt tokens processed,
11

---

Published in Transactions on Machine Learning Research (02/2026)
the total cost ranges from $10.31 for GPT-4o-mini to 8522.48 for o3-mini, representing more than 50-fold difference. Notably, reasoneng-enhnnced models (ol-mini, 03-mini, and DeepSeek-RI) exhibit substantially higher completion token consumption due to the generation of extensive intermediate reasoning tokens. For instance, 03-mini generates 110 million completion tokens, 11.7 times more than GPT-4o-mini, directly contributing to its elevated operational cost. In contrast, GPT-4o-mini demonstrates the best cost-effectivenes through its efficient token generation strategy, while Claude-3.7-Sonnn (11.2 million), incurs a total cost of $269.19 due to its higher pricing ($15/MTok for completion). The DeepSeek series models show competitive pricing under the RMB pricing structure, with DeepSeek-V? V3 requiring only 192.41 RMB (approximately $27). It is worth noting that compared with static benchmarks, e.g,, ZebraLogic (Lin et al., 2025), evaluating on NPPC is inherently more costly due to its ever-scalingness and the rigorous evaluation protocol. These cost metrics provide crucial economic considerations for researchers in large-scale evaluations where model inference and pricing strategies directly impact project feasibility.
despite moderate completion tokens
Table 4: Cost for online models
Model
Prompt
Completion
Cost
GPT-4o-mini
30964144 /5..5/MMook
9442548 ($0.6) (Tok)
$10.31
GPT-4o
30963606 ($2.5/MTor)
7786156 ($10/MTok)
$155.27
Claude-3.7-Somme
33799101 ($3/MTok)
11186272 ($15/MTod
$269.19 19
DeepSeek-Ve V3
31490957 ( M
16178388 (8RMB/ (BRMB/MTook
192.41RMB
DeepSeek-V3-22 V3-2503
31490957 (2RMB/MTON
31808451
CORMB/MToll
317.45RMB
DeepSeek-RI
31512557 (4RMB/MTod
95936418 (16RMB/ LLGMBB/MTok /MTok)
1661.03RMB
ol-mini
31360984
($1.1/MTok)
35161551 ($4.4/MTok)
$189.21
03-mini
31199884
($1.1/MTok)
110944621 ($4.4/MTok)
$522.48
6 Limitations and Future Work
Multimodal NP Problems. The first limitation of this work is only text-based NPC problems are considered. Extending NPPC to the multimodal domains represents promising direction. Games like StarCraft II, Minesweeper, Pokemon and Super Mario Bros (Aloupis et al., 2015), could form the foundation of multimodal version of NPPC. However, extending NPC problems to the multimodal domain presents significant challenges that require careful consideration and novel approaches. Two primary obstacles emerge in this endeavor: first, not all NPC problems are inherently suitable for multimodal representation, as demonstrated by problems like 3SAT which are fundamentally symbolic and lack natural visual components; second, maintaining the scalable difficulty characteristics essential to NPC problems becomes complex when incorporating images or videos that may exceed the input context windows of multimodal language models.
AI Agent with Tool Use. The second limitation of this work is that do not consider tool use by LLMs when solving NPC problems. LLMs equipped with tool-using capabilities are typically referred to AI agents (Wang et al., 2024a). Despite this limitation, the benchmark has significant potential to contribute to Al agent development by naturally encouraging tool use as problem difficulty scales. As problems become more complex, LLMs will increasingly need external tools to manage computational demands. This creates a natural progression toward agent capabilities, where models learn to decompose problems and leverage appropriate tools. Notably, we alrcady observe code generation in models attempting difficult NPPC problems, which can be viewed as form of tool creation, since these generated codes can be reused for future problem--olvingg
Unstoppable RL vs. Ever-Scaling NP Problems. The rapid progress in LLM reasoning capabilities through reinforcement lcarning (RL) presents an interesting dynamic when considered alongside ever-scaling NPC problems. Recent work (Liu el al., 2025a;b) demonstrate that the reasoning data generated by NPC problems can improve the general reasoning capabilities of LLMs. As models like DeepSeek-HH R1 and OpenAl o1/o3-mini demonstrate significant reasoning improvements through RL tochniques, NPPC provides a counterbalance by offering problems that can contimuuuly scale in difficulty. This creates an adversarial paradigm: RL improves model reasoning and NPPC scales to maintain challenging (Zeng et al., 2025).
12

---

Published in Transactions on Machine Learning Research (02/2026)
7 Conclusion
We propose Nondeterministic Polynomial Problem challenge (NPPC), an ever-scaling benchmark that is designed to evolve alongside LLM advancements. NPPC comprises three core components: i) npgym: a unified framework for generating customizable problem instances across 25 NPC problems with adjustable complexity levels; ii) npsolver: a flexible evaluation interface supporting both online APIs and offline local deployments; iii) npeval: a comprchensive toolkit for the systematic evaluation of LLMs across different problems, including the solution validity, reasoning errors, token efficiency. Our extensive experiments with state-of-tho-art LLMs demonstrate that: NPPC successfully reduces all models' performance to below 10% at extreme difficulties, confirming its uncrushable nature, ii) DeepSeek-R1, emerge as the most powerful LLMs, with DeepSeek-Ri R11 outperforming others in 7/12 problems, iii) Models exhibit distinct failure patterns, including cascading assumptions, manual computation errors, and reasoning repetition. To the best of our knowledge, NPPC is the first ever-scaling reasoning benchmark for reliable and rigorous evaluation of the reasoning limits of LLMs and suggesting the further improvements.
Slaude3..--ooneee and ol-mini
Acknowledgments
This work was partially supported by the Singapore Ministry of Education (MOE) Academic Rescarch Fund (AcRF) Tier 1 grant (Proposal ID: 23-SIS-SMU--087). The work described in this paper was partially supported by a grant from the Innovation and Technology Commission of the Hong Kong Special Administrative Region, China (Project No. GHH/299/22). This work was also partially supported by the Wallenberg A1, Autonomous Systems and Software Program funded by the Knut and Alice Wallenberg Foundation. The computations were enabled by the supercomputing resource Berzelius provided by the National Supercomputer Centre Linköping University and the Knut and Alice Wallenberg Foundation, Sweden. Any opinions, findings, and conclusions or recommendations expressed in this publications are those of the author(s) and do not necessarily reflect the views of the funding agencies.
References
Josh Achiam, Steven Adler, Sandhini Agarwal, Lama Ahmad, llge Akkaya, Florencia Leoni Aleman, Diogo Almeida, Janko Altenschmidt, Sam Altman, Shyamal Anadkat, et al. GPT-4 technical report. arXiv preprint arXiv:230s.08771 087777 2023.
Rishabh Agarwal, Max Schwarzer, Pablo Samuel Castro, Aaron Courville, and Mare G Bellemare. Deep reinforcement learning at the edge of the statistical precipice. In NewrIPS, pp. 29304 29304-29320, 2021.
Greg Aloupis, Erik D Demaine, Alan Guo, and Giovanni Viglietta. Classic Nintendo games are (computation- ally) hard. Theoretical Computer Science, 186:133-161) 2015.
Vidhisha Balachandran, Jingya Chen, Lingjiao Chen, Shivam Garg, Neel Joshi, Yash Lara, John Langford, Besmira Nushi, Vibhav Vincet, Yue Wu, and Safoora Youscfi. inference-time scaling for complex tasks: Where we stand and what lies ahead. arXiv preprint or arXix:2504.0020 2025.
BerriAL Litellm.
http://tttttbboomm//e/////t///// 2023.
Wei-Lin Chiang, Lianmin Zheng, Ying Sheng, Anastasios Nikolas Angelopoulos, Tianle Li, Dacheng Li, Banghua Zhu, Hao Zhang, Michael Jordan, Joseph E Gonzalez, et al. Chatbot arena: An open platform for evaluating 1mms by human preference. In ICML, 2024.
François Chollet. On the measure of intelligence. arXiv preprint arXiv:1911.0155f. 2019.
Karl Cobbe, Chris Hesse, Jacob Hilton, and John Schulman. Leveraging procedural generation to benchmark reinforcement learning. In ICML, pp. 2048-2056, 2020.
Karl Cobbe, Vineet Kosaraju, Mohammad Bavarian, Mark Chen, Heewoo Jun, Lukasz Kaiser, Matthias Plappert, Jerry Tworek, Jacob Hilton, Reichhro Nakano, et al. Training verifiers to solve math word problems. arXiv preprint or Xin:21 10. 14168, 2021.
13

---

Published in Transactions on Machine Learning Research (02/2026)
Stephen A Cook. The complexity of theorem-proving procedures. In Logic, automata, and computational complexily: The works of Stephen A. Cook; pp. 143-152. ACM, 2023.
Thomas Cormen, Charles E Leiserson, Ronald L Rivest, and Clifford Stein. Introduction to Algorithms. MIT press, 2022.
Pierluigi Crescenzi, Deborah Goldman, Christos Papadimitrion, Antonio Piccolboni, and Mihalis Yannakakis. On the complexity of protein folding, In Proceedings of the thirtieth annual ACM symposium on Theory of computing, pp. 597-603, 1998.
Leonardo De Moura and Nikolaj Bjørner. Z3: An efficient SMT solver. In International conference on Tools and Algorithms for the Construction and Analysis of Systems, pp. 537-340. Springer, 2008.
Xinrun Du, Yifan Yao, Kaijing Ma, Bingli Wang, Tianyu Zheng, King Zhu, Minghao Liu, Yiming Liang, Xiaolong Jin, Zhenlin Wei, et al. SuperGPQA: Scaling LLM evaluation across 285 graduate disciplines. arXiv preprint Xrx::22502. 14 739, 2025.
B Efron. Bootstrap methods: Another look the jackknife. The Annals of Stalistics, pp. 1-26, 1979.
Bradley Efron. Better bootstrap confidence intervals. Journal of the American statisticol Association, 82
(397):171-185, 1987.
Lizhou Fan, Wenyue Hua, Lingyao Li, Haoyang Ling, and Yongfeng Zhang. NPHardEval: Dynamic benchmark on reasoning ability of large language models via complexity classes. In ACL, pp. 4092 4114, 2024.
Daya Guo, Dejian Yang, Haowei Zhang, Junxiao Song, Peiyi Wang, Qihao Zhu, Runxin Xu, Ruoyu Zhang, Shirong Ma, Xiao Bi, al. DeepSeck-R1 incentivizes reasoning in LLMs through reinforcement learning. Noture, (45(8081):6333 638, 2025.
Rishi Hazra, Gabriele Venturato, Pedro Zuidberg Dos Martires, and Luc De Raedt, Can large language models reason? a characterization via 3-SAT. arXiv preprint arXiv:2408. 001.0120, 2024.
Dan Hendrycks, Collin Burns, Steven Basart, Andy Zou, Mantas Mazeika, Dawn Song, and Jacob Steinhardt. Measuring massive multitask language understanding. In ICLR, 2021.
Robert V Hogg, Elliot A Tanis, and Dale Zimmerman. Probability and Statistical Inference, volume 993. Macmillan New York, 1977.
Naman Jain, King Han, Alex Gu, Wen-Ding Li, Fanjia Yan, Tianjun Zhang, Sida Wang, Armando Solar- Lezama, Koushik Sen, and lon Stoica. LiveCodeBench: Holistic and contamination free evaluation of large language models for code. In ICLR, 2025. URL https: /openrvv/peerevier. het/formm?id-chtJTCCS
Carlos Jimenez, John Yang, Alexander Wettig, Shunyu Yao, Kexin Pei, Ofir Press, and Karthik R. Narasimhan. SWE-bench: Can language models resolve real-world github issues? In ICLR, 2024.
Richard M Karp. Reducibility among combinatorial problems. In 50 Years of Integer Programming 1958-2008 from the Early Years to the totte-of-the-Art pp.
Springer, 2009.
Woosuk Kwon, Zhuohan Li, Siyuan Zhuang, Ying Sheng, Lianmin Zheng, Cody Hao Yu, Joseph Gonzalez, Hao Zhang, and lon Stoica. Efficient memory management for large language model serving with pagedattention. In Proceedings of the 29th Symposium on Operating Systems Principles, pp. 611-61666 111-626, 2023.
Xiaozhe Li, Xinyu Fang, Shengyuan Ding, Linyang Li, Haodong Duan, Qingwen Liu, and Kai Chen. NP- Engine: Empowering optimization reasoning in large language models with verifiable synthetic NP problems. arXiv preprint arXio:2510.16476 2025.
Bill Yuchen Lin, Ronan Le Bras, Kyle Richardson, Ashish Sabharwal, Radha Poovendran, Peter Clark, and Yejin Choi. ZebraLogic: On the scaling limits LLMs for logical reasoning. orXie preprint 20110:2502.01100 2025.
14

---

Published in Transactions on Machine Learning Research (02/2026)
Huanyu Liu, Jia Li, Hao Zhu, Kechi Zhang, Yihong Dong, and Ge Li. SATURN: SAT-based reinforcement learning to unleash language model reasoning. arXiv preprinl or aixi:2200. Nio:2505.16368, 16368, 2025a.
Junteng Liu, Yuanxiang Fan, Zhuo Jiang, Han Ding, Yongyi Hu, Chi Zhang, Yiqi Shi, Shitong Weng, Aili Chen, Shiqi Chen, et al. SynLogic: Synthesizing verifiable reasoning data at scale for learning logical reasoning and beyond. arXiv preprint arXit:2505.1900 2025b.
Jinjie Ni, Fuzhao Xue, Xiang Yue, Yuntian Deng, Mahir Shah, Kabir Jain, Graham Neubig, and Yang You. MixEval: Deriving wisdom of the crowd from LLM benchmark mixtures. In NewrIPS, 2024.
OpenAl. OpenAl o3 and 04-mini system card 2025.
URL https://openai.com cow/index/
Shubham Parashar, Blake Olson; Sambhav Khurana, Eric Li, Hongyi Ling, James Caverlee, and Shuiwang Ji. Inference-time computations for LLM reasoning and planning: A benchmark and insights. arXiv preprinl arXiv:2502.12521, 2025.
David Rein, Betty Li Hou, Asa Cooper Stickland, Jackson Petty, Richard Yuanzhe Pang, Julien Dirani, Julian Michael, and Samuel R Bowman. GPQA: A graduate-lovel googlc-proof Q&A benchmark. In COLM, 2024.
Jeffrey Seely, Yuki Imajuku, Tianyu Zhao, Edoardo Cetin, and Llion Jones. Madoku-Benche https://github. /tt///akaanaT/Sudokuuu Bench, 2025.
Zafir Stojanovski, Oliver Stanley, Joe Sharratt, Richard Jones, Abdulhakeem Adefioye, Jean Kaddour, and Andreas Köpf. REASONING GYM: Reasoning enviromments for reinforcement learning with verifiable rewards. arXiv preprint ar Xxxv:2505.247000 2025.
Paolo Toth and Daniele Vigo. The Vehicle Routing Problem. SIAM, 2002.
Guanzhi Wang, Yuqi Xie, Yunfan Jiang, Ajay Mandlekar, Chaowei Xiao, Yuke Zhu, Linxi Fan, and Anima Anandkumar. Voyager: An open-ended embodied agent with large language models. Transactions on Machine Learning Research, 2024a. ISSN 2835-8856.
Yubo Wang, Xueguang Ma, Ge Zhang, Yuansheng Ni, Abhranil Chandra, Shiguang Guo, Weiming Ren, Aaran Arulraj, Xuan He, Ziyan Jiang, Tianle Li, Max Ku, Kai Wang, Alex Zhuang, Rongqi Fan, Xiang Yue, and Wenhu Chen. MMLU-Pro: A more robust and challenging multi-task language understaning benchmark. Tn NeurIPS Datasets and Benchmarks Track, 2024b.
Mingqi Wu, Zhihao Zhang, Qiaole Dong, Zhiheng Xi, Jun Zhao, Senjie Jin, Xiaoran Fan, Yuhao Zhou, Yanwei Fu, Qin Liu, et al. Reasoning or memorization? unreliable results of reinforcement learning due to data contamination. arXiv preprint arXiv:2507.1055. 2025.
Cheng Xu, Shuhao Guan, Derck Greene, M Kechadi, et al. Benchmark data contamination of large language models: A survey. arXiv preprinl arXiv:2406.0 04244, 2024.
Zhiyuan Zeng, Hamish Ivison, Yiping Wang. Lifan Yuan, Shuyue Stella Li, Zhuorui Ye, Siting Li, Jacqueline He, Runlong Zhou, Tong Chen, et al. RLVE: Scaling up reinforcement learning for language models with adaptive verifiable environments. arXie preprint ar arxiv:2511.070 073.11, 2025.
Linghao Zhang, Shilin He, Chaoyun Zhang, Yu Kang, Bowen Li, Chengxing Xie, Junhao Wang, Maoquan Wang, Yufan Huang, Shengyu Fu, et al. SWE-bench goes live! arXio preprint ar Xiv:2500 23419, 2025.
15

---

Published in Transactions on Machine Learning Research (02/2026)
Appendix
Contents
1 Introduction
1
2 Related Work
3
Preliminaries
4
4 Nondeterministic Polynomial-time Problem Challenge
5
4.1 Problem Suite:
npgym
5
4.2 Solver Suite: npsolver
4.3 Evaluation Suite: npeval
Results
5.1
Analysis of Performance
5.2
Analysis of Used Tokens
10
5.3
Analysis of Solution Errors
10
5.4
Analysis of Reasoning Failure Cases
11
5.5 Cost of Evaluations..
11
6 Limitations and Future Work
12
7
Conclusion
13
A Frequently Asked Questions (FAQs)
18
A.1 Why Ever-Scaling and the Four Desiderata?
18
A.2 Why Focusing NP (Specifically NPC) Problems?
18
A.3 Why Not Considcring More Complex Test-time Scaling?
19
A.4 Why Not Focusing on 3SAT Only?
19
A.5 Can Tool Use Crush NPPC?
................................
A.6 Determining the Difficulty Levels
................................
20
A.7 Selection of Models
21
A.8 Code and Leaderboard.
21
A.9 Correlation of Performance between NPPC and Other Benchmarks
21
A.10 Broader Impact Statement..
22
B Computational Complexity: P, NP, NP-complete and NP-hard
23
C Modules in NPPC
24
16

---

Published in Transactions on Machine Learning Research (02/2026)
C.1 Problem Suite: npgym
24
C.2 Solver Suite: npsolver
33
C.3 Evaluation Suite: inpeval
34
D Prompts and Responses
35
E List of NP-complete Problems
37
F Hyperparameters
40
G Full Results over Problems
41
H Performance over Problems
45
Tokens
49
J. Aha Moments
54
K Solution Errors
55
L Analysis of Reasoning Failure Cases
59
M Thorough Error Analysis of QwQ-32B
62
17

---

Published in Transactions on Machine Learning Research (02/2026)
A Frequently Asked Questions (FAQs)
A.1 Why Ever-Scaling and the Four Desiderata?
Why Ever-Scaling? LLMs are advancing at an unprecedented pace, making existing benchmarks obsolete quickly and posing a significant challenge for maintaining reliable evaluation. An ever-scaling benchmark can evolve alongside LLMs, iee, adapting dynamically to match the development of LLMs. The ever-scaling benchmark can address two core limitations in traditional benchmarks: i) short lifespan, where traditional benchmarks are easily crushed as LLMs rapidly improve, losing their ability to distinguish between models; ii) limited exploitability, where models can hack the answers in static benchmarks through overfitting or finding shortcuts to answers without genuine reasoning.
Why the Four Desiderate are Important? The four desiderata include:
Scaling over complexity. The benchmark can generate problems with continually increasing difficulty, e.g., larger input sizes, stricter constraints, etc. This property can prevent the benchmark from being solved to prevent obsolescence, and mirror the real-world problems, e.g., logistics and chip design, which grow in complexity as systems scale. The scaling over complexity implies if the LLMs solve the generated problem instances of the current difficulty level, the benchmarks can generate more difficult problem instances until the reasoning limits of them.
Scaling over the instance. The benchmark can generate infinite unique instances, even al the same complexity level. This property makes it impossible for LLMs to memorize the answers or simply overfit to patterns in static training data, and forces LLMs to reason about the underlying logic to ensure the fairness of evaluation. To mitigate memorization effects, researchers can randomly sample novel problem instances during evaluation to obtain reliable performance metrics.
Scaling over oversight. The benchmark provides an automated and cost-effective evaluation without any human intervention, i.c., the solutions can be verified efficiently even for arbitrarily complex problems. This property is critical for large-scale benchmarking as human evaluation is impractical for massive or highly complex benchmarks, therefore, automated verification is necessary for evaluating at scale.
Scaling over coverage. This property enables the benchmark to prioritize problems with broad applicability, thereby reflecting real-world utility and challenges. Consequently, advances demonstrated on the benchmark serve reliable indicators of progress on practical, real-world tasks.
A.2 Why Focusing on NP (Specifically NPC) Problems?
Why not P or NP-hard Problems? Problems in the P complexity class can be solved in polynomial time. When LLMs are equipped with code exccution capabilitics, they can generate and exccute algorithms to solve these problems directly. Consequently, such benchmarks become susceptible to trivial solutions through computational tools rather than genuine reasoning. Conversely, NP-hard problems, particularly those lacking polynomial-time verification procedures, present scalability challenges: as problem instances grow extremely large, efficient solution verification becomes intractable, potentially compromising the benchmark's ability to scale over complexity and oversight.
Why NPC Problems? NPC problems are the "hardest" problems in NP class and any other NP problems can be reduced to NPC problems in polynomial time. The absence of known polynomial-time algorithms for NPC problems ensures that current. benchmarks measuring performance on these problems cannot be trivially dominated through tool using. Furthermore, the polynomial-time verifiability of solutions enables efficient assessment of solutions generated by LLMs or AI agents even for large-scale problem instances.
World Relevance of Large-Scale NPC Problems. The ability to effectively solve large-scale NPC problems holds profound implications across numerous critical domains in modern society. In logistics and supply chain management, vehicle routing problems for major delivery companies like Amazon or FedEx involve optimizing routes for tens of thousands of vehicles across millions of delivery locations daily, while global supply chain optimization can encompass networks with hundreds of thousands of nodes. Computational biology relies heavily on solving NPC problems where protein folding prediction may explore conformational spaces with 10000 more possible states, and genome assembly for complex organisms processes billions
18

---

Published in Transactions on Machine Learning Research (02/2026)
of DNA fragments. In telecommunication and computer networks, resource allocation and network design problems routinely involve graphs with millions of nodes and edges, where even moderate-sized instances with thousands of variables become computationally prohibitive. Therefore, developing and evaluating methods capable of tackling NPC problems at truly large scales is not merely an academic exercise but a practical necessity with enormous economic and societal stakes. This makes NPPC particularly valuable as a benchmark: by providing an ever-scaling framework that can generate arbitrarily large NP-complete problem instances, NPPC enables rigorous evaluation of whether Al systems can bridge the critical gap between solving toy problems and addressing the massive-scale combinatorial challenges in real-world applications.
A.3 Why Not Considering More Complex Test-time Scaling?
The Majority Voting, Best of N, and even tools, e.g., domain-specific solvers, can further improve the performance of models (Parashar et al., 2025; Lin al., 2025). However, these approaches either necessitate multiple forward passes through the language model or incorporate auxiliary components such reward models or external tools to augment the reasoning process. Our primary objective is to investigate the reasoning capabilities of LLMs and these complex test-time scaling would be beyond the scope of this paper. We will tackle this in the future work.
A.4 Why Not Focusing on 3SAT Only?
3SAT is classic NPC problem with theoretical completeness, which provides a theoretically rigorous foundation for benchmarking. As an NPC problem, although all NP problems can be reduced to 3SAT, solely relying on reduction to 3SAT is impractical and reasoning benchmarks demand broader diversity:
Reduction overhead: The reduction process may incur significant computational overhead. Additional variables and constraints are often introduced when reducing non-trivial NP problems to specific NP- complete problem, c.g., reducing Traveling Salesman Problem (TSP) to 3SAT requires mapping the structure of the original problem into Boolean logic expression through an encoding mechanism, which introduces an exponential number of variables and clauses, significantly increasing the computational complexity and leading to hidden costs.
Loss of characteristics: Each specific NP problem has domain-specific information, c.g., structure and characteristics. For example, Traveling Salesman Problem (TSP) has graph structures, Bin Packing has combinatorial optimization characteristics, and Graph 3-Colourability (3-COL) has adjacency charac- teristics. Therefore, reducing NP problems to 3SAT and only considering 3SAT will cause the loss of problem specificity, e.g., structural semantics, which could be used to design more efficient heuristics approximation algorithms.
Lack of robustness: NP problems form the foundation of numerous real-world scenarios, which often exhibit, various conditions that cannot be adequately represented solely through 3SAT. As a reasoning benchmark, NPPC should encompass a variety of problem sizes and structures rather than concentrating exclusively on 3SAT to effectively evaluate the capabilitics and scalability of LLMs. Therefore, diverse set of complex NP problems that can closely mimic real-world challenges should be considered.
A.5 Can Tool Use Crush NPPC?
Tool use represents a significant advancement in LLM capabilities for tackling NPC problems in the NPPC benchmark, yet. fundamental computational barriers remain. When equipped with external tools such as code interpreters, symbolic solvers, or verification systems, LLMs would demonstrate substantially improved performance on NPPC tasks by offloading computationally intensive operations and leveraging specialized algorithms. For instance, tools enable models to execute exhaustive search procedures more reliably, verify candidate solutions programmatically, and utilize domain-specific hcuristics that would be difficult to implement through pure text generalion. However, despite these enhancements, tool-augmented LLMs still cannot fully solve NPC problems in the general case. The core limitation stems from the inherent computational complexity: while tools can accelcrate specific subroutines or handle particular problem instances more efficiently, they do not fundamentally alter the exponential worst-case complexity of NPC problems and we do not have the tools which can solve the NPC problems in polynomial time. Moreover,
19

---

Published in Transactions on Machine Learning Research (02/2026)
the effectiveness of tool use depends critically the model's ability to decompose problems correctly, formulate appropriate tool calls, and reason about the results. These capabilities remain imperfect even in state-of-the-art systems. Thus, while tool integration marks a meaningful step toward more capable problem-solving systems, NPPC would still serve a meaningful benchmark for tool-angmented LLMs.
A.6 Determining the Difficulty Levels
How to Determine the Difficulty Levels? For NPPC, we address this challenge through a two-stage method: we begin with manual configuration of problem parameters based on established computational complexity theory and domain expertise and then the humann-onffguree difficulty levels are further calibrated through systematic empirical testing with statc-of-tho-art LLMs. Specifically,
1. Human-defined difficulty parameters: We start with interpretable problem parameters. For SAT, this means specifying (num vvriables, num clauses) such as (3, 5), (4, 5), (100, 100). While we can confidently say (100, 100) is harder than (5, 5), distinguishing between similar configurations like (5, 4) versus (4, 5) is non-trivial.
2. L.LM- calibration: We use model performance for two specific purposes: i) Fine-grained ordering: Sorting problems of similar complexity for clearer visualization (e.g., Figure 5), particularly when human intuition cannot definitively rank them. ii) Range validation: Ensuring difficulty levels fall within a meaningful range, i.e., avoiding settings where all models achieve 100% (too easy) 0% (too hard) accuracy, neither scenario effectively benchmarks capabilities.
We want to note that this is not circular reasoning. We are not using LLM performance to define what makes problems hard; rather, we use it as a practical tool for (1) ordering problems within human-defined difficulty ranges and (2) validating that our chosen parameter ranges enable effective diffcrentiation between models. This two-stage approach ensures that problems' difficulty levels are both theorelicully grownded and practically meaningful for evaluating LLM capabilities.
Are the Generated Instances Truly Difficult for LLMs? YEs, our validation process confirms this through multiple measures: i) we observe consistent performance degradation across difficulty levels, indicating that our instances successfully challenge LLM capabilities, ii) different difficulty levels produce distinct failure modes, suggesting that instances test diffcrent aspects of reasoning ability, and iii) the difficulty progression holds across multiple LLM architectures, indicating robustness beyond specific model biases. Although our approach is conceptually simple, it can trully generate difficult. instances.
Why not Focusing on Hardest Instances? Our goal is to evaluate general reasoning capabilities rather than exploit specific failure modes. By providing graduated difficulty spectrum, we can assess reasoning development by tracking how LLM performance scales with problem complexity, identify capability boundaries to determine where different reasoning strategies break down, and support practical applications by focusing on difficulties relevant to real-world scenarios.
Why not Using Traditional Tools, e.g., Z3 (De Moura & Bjorner, 2008)? The difficulty experienced by traditional symbolic solvers does not necessarily translate to difficulty for LLMs due to fundamental differences in problem-solving approaches. First, traditional solvers use systematic search and logical inference, while L.MMs rely on pattern recognition and learned heuristics. Second, problems that are hard for symbolic methods due to search space explosion may be tractable for LLMs through pattern matching, and vice versa, therefore, the relationship between problem size and difficulty differs dramatically between symbolic and neural approaches. Third, traditional tools fail due to computational resource constraints, while LLMs fail due to reasoning limitations or training data gaps. Therefore, LLM-specific calibration is essential to create benchmarks that meaningfully assess the unique capabilities and limitations of LLMs. In examining 25 NPC problems across multiple domains, we observe that problem-specific tools, while potentially effective within their narrow scope, lack the generalizability required for comprehensive evaluation. Therefore, we do not rely on traditional computational tools as the primary metric for establishing problem difficulty levels in LLM evaluation frameworks.
20

---

Published in Transactions on Machine Learning Research (02/2026)
A.7 Selection of Models
Due to the limited budget, can only select. the representative models for the evaluation. Specifically, we choose the two representative offline medium-sized reasoning models, ie., QwQ-32B and DeepSeek-R1-322 and online advanced non-reasoning models, i.c., GPT--o-mini, GPT-4o, Claude-3.7-Somnet DeepSeck-V3. DeepSeek-V3-ee V3-2503, and online reasoning models, i.e., DeepSeek-R1, ol-mini, and o3-mini. For the more recent models, e.g,, o3, o4-mini, Gemini 2.5 Pro, Qwen 3, Llama 4, Claude-4, and GPT-5, we will add them in the next update of our benchmark.
A.8 Code and Leaderboard
We provide the screenshot of the leaderboard in Figure 11. The code and leaderboard can be accessed https://github. htt.s/tuuuu.ccc.---utete Sttp///UUDDIIAPPP....
Leaderbourd
Medel Filter:
Soarch:
Type to scash.
Sourch
Open-Souree?
Thas Palls
Sedect Columas Display:
Reasoning?
Usie
Trer
Paise
Macat:
Hank?
Average
Dale
MA11
Vertes Caver)
Seperatrig!
gox:
NDME
TSP:
Handiteeba Cyck)
Bis Packing!
0.63
9.51
3054
0.59
05
0.5
063
0152
035
0.55
0.43
Claade-
0.39
0.35
VS-2993
0.43
30240
0.5
04
0.26
0:56
0.57
el-miiii
0.34
N0LZ
045
0.44
0.23
0.22
0.41
0.39
0.3
6.27
Seeps
177
3054
0.42
0:88
0.29
Lif1-4o
306-11
0.11
6.18
DeepSiekk
R1-32B
0.17
X01
0.32
0.33
0.16
0.14
02
0.14
0.88
Figure 11: Screenshot of NPPC leaderboard
A.9 Correlation of Performance between NPPC and Other Benchmarks
Model
NPPC
MMLU
GPQA Diamond
LMArena
DeepSeek-R1
0.62
90.8
71.5
1396
03-mini
0.51
84.9
70.6
1348
Claude-3. 7-Sonnet.
0.49
86.1
68.0
1371
DeepSeck-V3-22 V3-2503
0.43
88.5
68.4
1392
ol-mini
0.34
85.2
60.0
1336
DeepSeek- V3
0.33
88.5
59.1
1358
QwQ-32B
0.3
59.5
1334
GPT-44
0.24
85.7
49.0
1335
DeepSeek-R1-32B
0.17
87.4
62.1
GPT-44-minni
0.14
82.0
1317
Table 5: Model performance over benchmarks.
21

---

Published in Transactions on Machine Learning Research (02/2020)
HPPC Diamand
MPPC
Pearson (-0. +-0.354, Spearman poo.346
Pearsen pw0.760, Spear po8.000
Pearson 623, Spearman pwd.60pp000000
30-
3340
-350
ScOTe
65
-350
34
0.2
0.3
0.4
2.5
0.5
0.2
0.3
0.4
0.5
0.2
0.3
0.4
0.3
0.5
Score
NPPC
Figure 12: Correlation between NPPC and established benchmarks.
Correlation (Pearson)
To validate the effectiveness of NPPC reasoning bench- mark, we analyze its correlation with three widely-used eval- uation metrics: MMLU (Hendrycks et al., 2021), GPQA Diamond (Rein et al., 2024), and IMArena (Chiang et al., 2024). We compute both Pearson correlation coefficient (for linear relationships) and Spearman rank correlation coeffi- cient (for monolonie relationships) across the 10 considered representative models. As shown in Figure 12, NPPC demon- strates strong positive correlations with both GPQA Dia- mond (Pearson's r = 0. 0.798, p = 0.010; Spearman's p 0.800, = 0.010) and LMArena (r = 0.821, = 0.007; = 0.833, p = 0.005), both statistically significant at the < 0.05 level. The correlation with MMLU shows a positive trend but does not reach statistical significance (r 0.553, p = 0.123), likely reflecting MMLU's broader emphasis factual knowledge Figure 13: Correlation matrix of benchmarks. alongside reasoning capabilities. These results provide sev- eral important validations. First, the strong correlation with GPQA Diamond, graduate-level science reasoning benchmark, confirms that NPPC effectively captures complex reasoning abilities required for advanced problem-solving. Second, the strong correlation with LMArena, a human preference-basee evalua- tion platform, demonstrates that NPPC performance aligns well with practical model utility real-world applications. The correlation matrix in Figure 13 provides a comprehensive view of these relationships.
NFCC
1,000
0.353
2.795
0.821
1.50
0.75
0.553
1.000
0.339
OPC4 Dumnn
-0.75
0.821
0.881
5:710
-1.00
NPFC
A.10 Broader Impact Statement
NPPC provides a scalable framework grounded in complexity theory for tracking progress computational reasoning, which can inform development of AI systems for scientific computing, optimization, and algorithm design. The NPPC benchmark may also raise several important considerations:
Computational and Environmental Costs. The ever-scaling nature of NPPC requires substantial computational resources, particularly as problem difficulty increases. Large-scale evaluations may result in significant energy consumption and carbon emissions. Future work should explore methods to maintain rigor while reducing computational costs through efficient subset selection or adaptive evaluation protocols. Risk of Overfitting to Synthetic Tasks. Models could specifically optimized for NPPC without corresponding improvements in real-world reasoning. This could lead to overfitting to benchnark-speeffic patterns or exploitation of artifacts rather than genuine algorithmic understanding. NPPC should be viewed as component of comprehensive evaluation, not singular optimization target. We discourage training practices that narrowly target NPPC performance at the expense of general capability development, real-world robustness, or safety considerations.
Scope and Interprctation of Results. High NPPC performance demonstrates proficiency in structured computational reasoning but should not be interpreted as evidence of general intelligence or real-world reliability. We call on researchers to interpret results within proper context and avoid overstating capabilities based on benchmark performance alone.
22

---

Published in Transactions on Machine Learning Research (02/2026)
B
Computational Complexity: P, NP, NP-complete and NP-hard
NP-hard
NP-complete
NP
P
Figure 14: The relation between P, NP and NP-complete
P. The class P consists of decision problems that can be solved by a deterministic Turing machine polynomial time. In practical terms, these are problems for which efficient algorithms exist. The time required to solve these problems grows polynomially with the input size (n); such as O(n), On or O(n²). Examples include sorting, searching in sorted array, and determining if number is prime.
NP. NP contains all decision problems for which solution can be verified in polynomial time. Every problem in P is also in NP, but NP may contain problems that are not in P. The key characteristic is that if somcone gives you a potential solution, you can quickly check whether it's correct, even if finding that solution might be difficult. Examples include the Boolean satisfiability problem and the Traveling Salesman decision problem.
No-copllete (NPC). No-complete problems are the "hardest" problems in NP. A problem is NP-complete if: i) It belongs to NP, ii) Every other problem in NP can be reduced to it in polynomial time. This means that if an efficient (polynomial-timg solve all problems in NP efficiently. The first proven NP-complete problem was the Boolean satisfiability problem (SAT). Other examples include the Traveling Salesman Problem, Graph Coloring, and the Knapsack Problem. The question of whether P-NP (whether every problem with efficiently verifiable solutions also has efficiently computable solutions) remains one of the most important open questions in computer science.
algorithm were found for any NP-complete problem, it could be used to
NP-hard Problems. A problem is NP-hard if every problem in NP can be reduced it in polynomial time, but unlike NPC problems, NP-hard problems need not be in NP themselves (i..., they need not be decision problems or have efficiently verifiable solutions). This makes NP-hard broader class that includes optimization versions of NPC problems (e.g., finding the minimum vertex cover rather than deciding if one of size & exists), as well as problems strictly harder than NP (e.g., certain problems in PSPACE or EXPTIME). In practice, many real-world applications involve NP-hard optimization problems where the goal to find optimal or near-optimal solutions rather than simply verify their existence.
23

---

Published in Transactions on Machine Learning Research (02/2026)
C Modules in NPPC
C.1 Problem Suite: npgym
Interface. We introduce пpgуm, problem suite containing 25 NPC problems with unified gym-style interface for instance generation and solution verification. Each environment defined by a problem name and its corresponding hyperparameters, enabling the generation of unlimited problem instances and example solutions. Difficulty can scaled by adjusting these paramcters. npgymm also supports automatic verification of solutions produced by large language models (LLMs). New problems can be added easily by implementing two core functions and providing a problem description for prompt generation.
class NPEnV:
def Linit__ (self, problem. name, level): self problem_nane problen_name
sevel level
self generate wtt.eeeaeeenttteeeeeeeeee instance, self._ ver..,,eriyy self get___ttstttteeeeeeaae
def -get_ www.iastance_ggnerttooot (self)
ap-gy=_folder "./apgym/npe"
problem_path PROBLEM2PATH [self problen_name)
generate_instan importlib.... wowpoooooood.elpprooee......oeee ceaterteeeeraeeee.. generate generate_instance instance
verify_solution importlib.. ittpllibiiaport_ndduuue (rr. verify solution soltiit
return generate, intratteinstanee, verify_
24

---

Published in Transactions on Machine Learning Research (02/2026)
Variables to Scale. Table 6 lists the variables to scale for each of the 25 No-comleete problems.
Table 6: NPC problems in NPPC and the variables to scale
Type
Problems
Variables scale
3SAT
num him__ariables, num num_ _lluusssusess_ mum nodes, cover_size n
Vertex Cover
3DM
TSP
num cities target Lenget__enghh num nom_nodes, directed num nodes, num edges num items, bin can__ccpatty, num bins num nodes, target leaves low, high num elements, n,
Hamiltonian Cycle
3-COL
Core
Bin Packing
Max Leaf Span Tree
QDE
Min Sum of Squares
Superstring
Bandwidth
num nodes, bandwidth
Clique
num nodes, clique size num nodes, ind set size num mod_ss k, odge_ num elements, numn subsets num elements, num subsets, num disjoint sets num elements, num subsets num eleements num__set,, k n, max value num elements, max value n, m min sin__alue,, max max_value value num element, num sen_ttipplessss num elements,
Independent Set
Dominating Set
Set Splitting
Set Packing
X3C
Extension
Minimum Cover
Partition
Subset Sum
Hitting String
Quadratic Congruences
Betweenness
Clustering
25

---

Published in Transactions on Machine Learning Research (02/2026)
Difficulty Levels. We define and release problem-specifie difficulty levels for each of the 25 core problems included in our benchmark. Each problem includes approximately 10 levels of increasing complexity, determined primarily by theoretical factors such as search space size and validated through empirical testing using DeepSeck-RR RI and GPT-4o. npgym allows scamless extension to higher diffculty levels as more powerful models become available.
3-Satiafiability (3-SAT)" : {
1: ("aum_variables": 5, "num_clauu clauses" 5},
2: ("aum_variables", 15. "aum_clauses" 15).
3: ("mun_variables"; 20, "num_clauses": 20),
4: ("nun_variablea", 25, "aun_clauses": 25),
5: ("mum_variablea"; 30, "aum_clauses": 30),
("aum_variables". 40, "nun_clauses": 40),
7: ("mun_variables": 50, "nun_clauses": 50),
8: ("num_variables": 60, "mun_clauses"; 60),
9: ("mum_variables"; 70, "mun_clauses"; 70),
10: ("aua_variables" 80, "nun_clauses"" 80),
},
"Vertex Cover": {
1: ("aum_nodee" 4, "cover_aize": 2}.
2: {"aum_nodes 8, "cover_aize". 3).
3: ("aum_nodes" 12, *cover_size" 4),
4: ("aum_nodes, 16, "cover_size: 5),
5: ("aum_nodes": 20.
"cover_size": 10),
6: ("aum_nodes": 24.
"cover_size": 12),
7: ("aum_nodes": 28.
"cover_size": 14),
8: ("num_nodes":
"cover_size": 16),
9: ("num_nodes" 36,
"cover_size;; 18),
10: ("nun_nodes") 40,
"cover_size"; 20),
},
Clique":
1: ["num_nodes": 4, "clique_size": 2),
2: {"num_nodes* 8, "clique_size": 4),
3: ("aum_nodes) 12, "clique_aize", 6),
4: ["aum_nodes 14, "clique_size" 7),
5: ("num_nodes": 16, "clique_size" 8),
6: {"num_nodes 18,
"clique_size" 9},
7: ("aum_nodes": 20. "liqqe__ize"; 10).
8: ("aum_nodes) 22. "clique_aize" 11).
9: ("num_nodes") 24, "llique_ezze 12).
10: ("nun_nodes": 26, "clique_size"; 13),
11: ("nun_nodes": 28, "clique_size": 14),
12: ("num_nodes": 30, "clique_size": 15).
13: ("nun_nodes" 40, "clique_size" 20),
}.
"Independent Sat":
1: ("num_nodes") "ind_sat_size"; 2),
2: ["nun_nodes" 8, "ind_set_size": 4),
3: ("num_nodes": 12, "ind_set_size": 6),
4: {"num_nodes"; 16, "ind_set_size": 8),
8: {"aum_nodes": 20, "ind_set_size". 10)
6: ["aum_nodes 24, "ind_set_size": 12).
7: ("aum_nodes" 26,
"ind_set_eize": 13),
8: ("num_nodes" 28,
"ind_set_eize": 14),
9: ("num_nodes" 30,
"ind_set_size"" 15),
10: ("num_nodes": 32, "ind_set_si2e": 16).
11: ("num_nodes": 34, "ind_set_si2e" 17).
12: " 36, "ind_set_size": 18),
13: ("num_nodes"; 48, "ind_set_size"; 24).
}.
"Partition":
1: {"n": "max_value": 1),
2: {"n": "nax_value": 40)
3: ("n"; 10, "max_value": 100),
["n": 20, "max_value": 200),
["n": 30, "max_value": 300),
26

---

Published in Transactions on Machine Learning Research (02/2026)
6: ["n": value"; 400).
7: ["n": "max_value": 500),
8: ["n": "max_value": 550),
9: ["n": 60, "max_value": 600),
10: ("n": 65, "max_value": 650),
11: {"n": 70, "max_value": 700).
12: ("n": 75, "max_value": 750),
13: ("n": 80, "nax_value": 800),
},
"Subaet Sum": {
1: {"aum_elements"; 5, "max_value"; 100},
2: ["mum_elements': 10, "max_valuee 100),
3: ("num_elements": 20, "max_value": 2003,
4: ("num_elements: 40, "max_value": 400},
5: ("mum_elements": 80, max_value" 800),
6: ("num_element I'aum_elements": 100, "max_value": 1000),
7: ("num_elementar 120, "max_value": 1200],
8: ("aum_elemente) 160, "max_value": 1000).
9: {"num_ ("aun_elements": ("aun_elements": 200,
"max_value": 1600).
"max_value": 2000)
("nun_elementa": 200,
'max_value"; 1000)
12: ("nun_elements" 400,
"max_value" 2000).
13: ("aun_eleeenta" 600,
"max_value" 2000)
}.
*Set Packing":
1: ("mun_elements', 10, "num_subsets". 10, "nun_disjoint_sets" 2},
2: ("num_elemente 40, "num_subsets"; 40,
83,
3: ("mun_elements"; 100, "aun_subseta"; 200, "mun_die@oint_sstt=" 50).
4: ("num_elements 100, "nun_aubsets": 400, "mum_ditjoint__ett"" 30).
6: ("num_elenents": 100,
"nun_subsets": 500, "nun_disjoint_sets": 30),
6: ("num_elements 100,
"nun_subsets": 600, "nun_disjoint_sets": 30),
7: ("aum_elemente" 100,
"aun_subsete": 800, "pun_disjoint_eett=": 30),
8: ("num_elementer 100,
"nun_aubsets": 1000, "mun_diejjontt_eeta""" 30),
9: ("mum_elements"" 200,
"nun_aubsets"; 400, "nun_disjoint__etta": 60),
10: ("nun_elements": ": 200,
"num_subsats"; 800, "mun_diajoint_eeta"" 60}
("mun_elementa"" 400,
"nun_subaete" 1000, "muu_dlejoint_eete"" 200).
"Set Splitting":
1: ""num_element"" 5, "aun_subsets"; 5)
2: ("aum_elements 10, "nun_subsets"; 10).
3: {"num_elens "emumeeemmnts" 10.
"num_subsets": 50}.
4: "'aum_elementer 10, "num_eubsete": 100).
5: ("num_elements
10,
"num_subsets"; 200),
6: {"num_ "rruu_elements": 100,
"aun_subseta": 100),
7: ("num_elementer 100,
"aun_aubseta": 200),
8: "'aum_elementa": 10,
"num_subsets": 500).
9: ("num_elements 10, "nun_subsets": 1000},
10: ("nun__lements"" 16, "nun_subsets": 500},
11: ("mun_elementa". 20, "aun_subsets": 500),
}
Shorttstt Common Superstring": {
1: {"n": 10, "k": 5},
2: {"n": "k": 10).
3: ("n":
"g": 20).
["n": 80,
"x": 40).
5: {"n": 100,
"k": 50},
6: {"n": 100.
"k" 100),
7: {"n": 100.
"k" 200).
8: {"n": 200.
"k" 200).
9: {"n": 300,
"k": 400),
10: {"n": 300,
"k": 600},
>,
"uuadratic Diophantine Equations": {
1: ["lou": 1, "high" 50},
2: ["lou": 1, "high" 100).
3: {"lov": 1, "high" 500),
4: ("lou": 1, "high": 1000),
5: {"lou": 1, "high": 5000),
27

---

Published in Transactions on Machine Learning Research (02/2026)
6: ("low": 1, "high": 10000}.
7: ["lou": 1, "high": 50000}.
8: ("lou": 1, "high": 80000)
9: ["lou": 1, "high": 100000),
10: ("low": 1, "high": 200000}
}.
Quaddratic Congruences":
1: {"min_value": 1, "max_value": 100),
2: ("min_value": 1, "max_value": 1000}.
3: ("min_value": 1, "max_Value": 10000)
4: ("min_value": 1, "max_Value": 50000)
6: ("min_value": 1, "max_value": 100000).
6: ("min_value": 1, "max_value": 300000),
7: ("min_value": 1, "max_value": 500000)
8: ("min_value": 1, "max_value": 800000),
9: ("min_value": 1, "max_value": 1000000},
10: ('min_value":
"nax_value": 3000000)
}.
"3-Dimensional Matching (3DN)":
("n": 4)
2: ["n": 8).
3: {"n": 12).
4: {"n": 15).
6: {"n": 20).
6: {"n": 25),
7: {"n": 30),
8: ("n": 40),
9: ("n": 50},
10: ("n": 60),
},
"Travelling Salesman (TSP)": {
1: ("sum_cities":
*target_length" 100). ,
2: ("sum_cities";
"target_length: 100).
3: ("num_cities"; 10, "target_length"" 100),
4: ("num_cities": 12, "target_length"" 100),
5: ("aum_cities": 15, "target_lengtä": 100).
6: ("aum_cities"
"target_lengtà"". 200),
7: ("num_cities": 20, "target_lengta"". 200),
8: ("num_cities": 25, "target__engtà".. 200),
9: {"num_cities") 30, "target_lengta"" 200).
10: ("nun_citiea"" 40, "target_length" 300).
}.
"Dominad
"Dominating Set":
1: {"num_nodes" : 10, "k": 5, "edge_prob": 0.3),
2: ("num_nodes' 15, "k": 5, "edge_prob": 0.3),
3: ("num_nodes": 30, "k" 15, "edge_prab": 0.3).
4: ("num_nodes" 50, "k": 20, "edge_prob": 0.3),
6: {"num_nodes": 70, "k": 20, "edge_prob": 0.3),
6: ("aum_nodes": 100, "k": 20. "edge_prob"; 0.3),
7: ("num_nodes": 70, "k" 20,
"edge_prob": 0.2),
8: ("num_nodes": ao, "k": 20,
"edge_prob": 0.2),
9: ("num_nodes": 100, "k": 20,
"edge_prob"; 0.2),
10: ("nun_nodes"; 150. "k":
"edge_prob"; 0.2),
11: ("nun_nodes"; 160, "k":
"edge_prob"; 0.2),
12: ("num_nodes"; 180, "k" 15, "edge_prob"; 0.2).
},
"Hitting String":
1: {"n": 5, "m" 10).
2: {"n": 5. "m" 20).
3: {"n": 10, "x": 20),
4: {"n": 10, "I": 30),
5: ("n": 10, "n": 40),
6: ("n": 10, "x": 45),
7: ["n": 10, "x": 50),
8: ("n": 10, "x": 55),
9: {"n": 10, "n": 60),
10: ["n": 10, "n": 70).
28

---

Published in Transactions on Machine Learning Research (02/2026)
"Hamiltoniam Cycle*:
1: ("dun_nodes"; 5, "directed": False),
("dun_nodes": 8, "directed": False),
("num_nodes" 10, "directed": False),
4: ("nun_nodes": 12, *directed": False},
5: {"aum_nodes": 16. "directed": False).
6: ("aum_nodes": 18. "directed": False),
7: {"nun_nodes": 20,
"directed": False},
8: ("num_nodes": 22,
"directed": False),
9: ("num_nodea" 25,
"directed"; False),
10: ("num_nodes"' 30,
"directed"; False).
},
"Bin Packing": {
1: {"num_items 10, "bin_capacity": 20.
"num_bins": 3
2: ("num_items": 20, "bin_capacity": 30,
"num_bins": 3),
3: ("num_items". 30, "bin_capacity": 30,
"num_bins". 3)
4: ("num_items": 40, "bin_capacity": 30,
maum_bins". 3),
5: ("aum_items":
"bin_capacity"; 50.
"num_bins";
6: ("aum_iteme)
"bin_capacity":
"aum_bins":
7: ("aum_items items 70, "bin_capacity": 50,
"aum_bins": 5)
("num_items" 80, "bin_capacity": 50,
"num_bins":
9: ("num_items) 80, "bin_capacity": 30
"aum_bins"; 10)
10: ("num_items"; 100, "bin_capacity" 50, inum_bins": 10).
}.
"Exact Cover by 3-Sets (X3C)": {
1: ("num_elements" 3, "nun_subaets': 6),
2: ("num_elements) 4, "nun_subsets": 8),
3: ("mun_elements"; 5, "aun_subsets"; 10),
4: ("num_elementer 7, "num_subsets": 14),
6: ("num_elements": 8, "nun_subsets": 16),
6: ("num_elements) 10, "nun_subsets"; 20),
7: ("aum_elements": 15, "num_subsete": 30),
8: ("num_elements" 20, "num_subsets": 40),
9: ("num_elements". 25, "num_subsets": 50),
10: ("nun_elements" 30, "aum_aubseta" 60),
}.
"Minimum Cover":
["num_ell : "aun_sets"; 10, "k" 3),
2: ""aum_element" 10, "num_sets": 20, "x": 5).
3: {"aum_elements 10, "num_sets": 30. "x": 5).
4: ("aum_elemente 15. "num_sets": 20. "x": 8).
5: "rauu_eeemeentr 15.
"num_sets": 30, "x": 10).
6: {"num_elenn) ""mum_elements": 20,
"num_sets" 40, "k": 10),
7: "'aum_elements"" 25,
"num_sets": 50, "k": 10),
8: ("num_elemente) 30,
"num_sete"" 60, "x": 10),
9: ["num_eil : 35,
"num_sets": 70, "x": 10).
10: ("nun_elements"; 40, "num_sets": 80, "k": 10),
11: ""nun_elements": 46, "num_sets": 90, "k": 10),
12: ("aun_elements": 50, "aum_seta"; 100, "x": 10).
13: ("aun_elements": 55, "aum_sets": 110, "x": 10).
14: ("nun_elements": 60, "aum_sets": 120, "x" 10),
15: ("nun_elements"; 65, "aun_sets": 130, "x" 10),
16: ("mun_elementa"; 70,
raun_seta": 140,
10).
}.
"Graph 3-Colourability (3-COL)*: {
1: {"num_nodes"; 5, "num_edges" 8),
2: {"aun_nodes": 8, "num_edges 12).
3: ("num_nodes": 10, sagn_"dges": 20).
4: {"num_nodes": 15. "nus_edges": 25).
6: {"nun_nodes":
15, "nun_edges": 30),
6: {"nun_nodes 15, "nun_edges": 40),
7: ("nun_nodes" 20, "nun_edges": 40),
8: ("num_nodes 20, "nun_edges": 45),
9: ("num_nodes, 30, "nun_edges": 60),
10: ""nun_nodes"; 30, "nun_edges": 80),
},
"Clustering: {
1: Stnum_elementer "b": 10),
29

---

Published in Transactions on Machine Learning Research (02/2026)
2: ("aum_elements
"b": 10).
3: ["num_ "'aun_elements:; 15, "b": 10),
4: ("aum_elenee "'aumeeleentt": 18, "b": 10), ("num_eless
6: : 20, "b": 10),
30, "b": 10),
7: ("aum_elemente 40, "b": 10),
8: ("aum_elemente 50, "b": 10),
9: {"num_ ""num_elements'; 60, "b": 10),
10: ("nun_elsmenta" 70, "b": 10),
},
"Betxeenneas";
1: ""num_element" 3, "num_triples"; 1).
2: ("num_element", 4, "nun_triples": 2}.
3: ("num_elemenn 5, "num_triples": 3)
4: ("mun_element": 6, "num_triples": 4),
5: : 7, "sum_triples": 5),
6: ("mum_element"; B, "sun_triples": 6),
}.
"Minimum of Squares*:
("num_ ("aum_elements": ["num_ ("mun_elements": 50, "x": 8).
"x": 5).
3: ("num_elements 100. "k": 8),
4: ""aum_elemente" 100. "k": 5),
5: ("aum_elemente" 100. "k": 4),
6: {"num_elen ("num_elenents": 100, "k": 3),
7: ("nun_elements": 200, "k": 10),
8:
200, "k": 4h,
9: ("mun_elements": 200,
"k": 3),
10: ("mun_elements") 300, "k": 3),
},
"Bandwidth": {
1:
3, "bandvidth": 2),
2: ["mum_nodes" 4, "bandvidth": 2),
3: ("num_nodes":
4: ("num_nodes": "bandvidth": 3),
"bandvidth": 3),
5: ("aum_nodes": "bandwidth": 2).
6: ("aum_oodes": "bandwidth": 3),
("num_nodes" 6, "bandwidth": 2),
8: {"num_nodes"; 8, "bandwidth": 3),
9: {"num_nodea": 7, "bandvidth"; 2),
10: ("dun_nodes"" 8, "bandvidth"; 2}.
},
"Maximum Leaf Spanning Tree": {
1: ("nun_nodes" 5, "target_leaves" 2),
2: ("num_nodes) 10, 'target_leaves"; 5),
3: "Vnum_nodes""" 20, "target_leaves" 10),
4: ("num_nodes" 30, "target_leaves": 20),
6: {"num_nodes": 40, "target_leaves": 30),
6: ("aum_nodes": 60, "target_leaves": 50)
7: ("num_nodes": 70,
target_leaves"; 60)
8: ("num_nodes": 80, "target_leaves": 65).
9: ("num_nodes": 90, "target_leaves"; 76).
10: ("den_nodes"; 100, "target_leavea", 80),
30

---

Published in Transactions on Machine Learning Research (02/2026)
Solution Errors. There are two fundamental error categories: problem-independeni errors and problem- dependent errors. Problem-independent errors are general errors that arise from external factors unrelated to the problem's intrinsic characteristics and all problems have these types of errors. Problem-independent errors include JSON ERROR (JSON not found or JSON parsing errors), and VERIFICATION ERROR (output format mismatches or structural validation failures). Problen-dependent errors originate from the problem's inherent complexity, which are defined based on problem specificity. A comprehensive illustration of the errors is displayed in Table 7.
31

---

Published in Transactions on Machine Learning Research (02/2026)
Table 7: A comprehensive illustration of errors.
Problem
Error Type
Description
JSON ERROR
JSON not found.
VERIFICATION ERROR
Wrong output format.
ERROR
The solution length mismatches the number of variables.
3SAT
ERROR 2
Some clauses are not satisfied.
ERROR
Wrong solution format.
ERROR
The cover empty.
Vertex Cover
ERROR 3
Invalid vertex index, i.c., above the max or below the min. The cover size exceods the limit.
ERROR
ERROR
Some edges are not covered.
ERROR
Not all triples in the matching are in the original set. The size of matching is wrong
3DM
ERROR 2
ERROR 3
The elements in the matching are not mutually exclusive.
ERROR
Tour length mismatches mumber of citics. Invalid city index, i.e, above the max or below the min.
ERROR
TSP
ERROR 3
There exists cities not be visited exactly once. Tour length exceeds target length.
ERROR 4
ERROR
Path length is wrong.
ERROR
Path does not return to start. Not all vertices visited exactly once. There exists invalid vertex in path.
Hamiltonian Cycle
ERROR 3
ERROR
ERROR 5
There exists invalid edges in path.
3-COL
ERROR
The two nodes of an edge have the same color
ERROR
Solution length mismatches the number of items. Invalid bin index.
Bin Packing
ERROR 2
ERROR 3
The total size exceeds bin capacity.
ERROR
Solution length mismatches the number of vertices.
ERROR
There exists invalid edges in solution. The solution does not have exactly one root.
Max Leaf Span Tree
ERROR 3
ERROR 4
The solution doesn't 't span all vertices. The number of leaves in the solution is less than target.
ERROR
ERROR ERROR 2
Solution length mismatches the number of integers.
There exists non- non-positive values in the solution.
QDE
ERROR 3
The equation does not hold.
ERROR
Solution length mismatches the number of elements. The number subsets exceeds the set limit.
Min Sum Square
ERROR
ERROR 3
The sum exceeds the limit J.
ERROR
Wrong solution format. The solution length exceeds the limit. Some string not the substring the solution.
Superstring
ERROR 2
ERROR
ERROR ERROR
Layout length mismatches the number of vertices.
Bandwidth
Layout is not permutation of vertices.
ERROR 3
There exists edge exceeds the bandwidth limit.
32

---

Published in Transactions on Machine Learning Research (02/2026)
C.2 Solver Suite:
npsolver
We introduce npsolver, solver suite that provides unified interface for both online (API-based) and offline (local) models. The unified interface includes: i) Prompt Generation, which constructs problem- specific prompts dynamically using the designed prompt templates shown in Appondix D, inchuding problem descriptions, in-context examples, and target problems: ii) LLM Completion, which invokes either online or offline LLMs generate responses from the constructed prompis; iii) Solution Patraction, which designs regular expressions to parse JSON outputs from the LLMs' responses, ensuring all online and offline LLMs Use the same JSON validation pipeline; iv) Error Reporting, which standardizes error messages. Through the unified interface, npsolver enables both online and offline models to share common workflow. Through this unified pipeline, npsolver enables consistent evaluation and analysis for both online and offline models. For each problem, difficulty level, and model, npsolvvr stores detailed records including the problem instance, example solutions, full LLM responses, extracted solutions, input/output token counts, error messages, solution correctness, and reasons for failure-in in pickle file facilitate failure case analysis. The list. of models integrated in npsolver is shown in Table
Table Online and oflline models considered in this paper via upsolver.
Type
Models
Version
Provider
GPT-4o-mini
gpt-4oommini-2224-07-11
OpenAT
GPT-4o
8pt-4o-2024408--66
OpenAl
ol-mini
01-mini-2024-09-12
OpenAI
Online
03-mini
03-mmii--2025-01-31
OpenAI
DeepSeck-V2. V3
dcepseek-v3-221226
Huoshan
DeepSeek- V3-2503
deepseek-v3-255022
Huoshan
DeepSeek-R1 Claude-3.7-Sonnet
deepseee::112250120
Huoshan
claude33-7somnne-22255022
Anthropic
QwQ-32B DeepSeek-R1-32B
Qwen/QwQQ-3B
N/A
Offline
deepseck-ai, Deseeaaaaaaeeeeeee....iiiiiii.e
N/A
Online. The online state-of-the-art LLMs, c.g,, ol 01/33-iini and DeepSeck-v3/Rl RRR, can be accessed through APIs without local computational overhead. However, these online models have dependency on network stability and API costs with token usage. npsolver supports multiple providers, e.g., OpenAI, through modular API clients. We implement efficient batch processing with LiteLLM, which minimizes the latency during parallel problem-solving.
Offline. Open-weight. LLMs, e.g., QwQ-32B and Deepseek-R1-321. can be accessed by deploying them locally. This allows for GPU-accelerated, sigh-throughput inference while avoiding APl-related costs. Offline models are deployed using vLLM, with hyperparameters- such as temperature and maximum token mangh-manually configured according their official technical documentation.
33

---

Published in Transactions on Machine Learning Research (02/2026)
C.3 Evaluation Suite: npeval
rpperal employs stalistically rigorous sampling strategy. For each dilficulty, the aggregated performance over different independent seeds, with 30 samples generated per seed, aligning with the minimum sample size for reliable statistical analysis (Hogg et al., 1977), are considcred. This sampling design, i.c., sampling 90 instances total per difficulty level for each problem, balances budget constraints while mitigating instance-specific variance.
Evaluation Metrics. rliable (Agarwal al., 2021) an open-source Python library designed to enable statistically robust evaluation of reinforcement learning and machine learning benchmarks. Inspired by rliable, npeual provides the following 4 evaluation aggregate metries:
Mean: Mean is standard evaluation metric that treats each score equally and calculates the overall mean across runs and tasks.
Interquartile Mean (TQM): IQM trims extreme values and computes the interquartile mean across rums and tasks smooth out the randomness in responses. IQM highlights the consistency of the performance and complements metrics like mean/median
avoid outlier skew.
Median: Median represents the middle value of the scores by calculating the median of the average scores per task across all runs, which is unaffected by extreme values.
Oplimality Gap (OG): OG measures the average shortfall of scores below a predefined threshold where all scores above y are clipped to y, so as to quantify and penalize the underperformance, making it less susceptible to outliers compared to mean scores.
To quantify uncertainty in aggregate metrics, e.g. IQM, npeval employs stratified bootstrap confidence intervals (SBCIs) (Efron, 1979; 1987) for the performance interval estimation. SBCTs use stratified resampling within predefined strata, e.g., difficulty levels, to preserve the hierarchical structure of the evaluation data, reduce bias, and provide statistically sound interval estimates.
Comprehensive Analysis. Based on evaluation metrics, npenal provides a comprehensive analysis of the LLMs' performance over the problems and difficulty levels, including the full results for each problem, each model and each level (Appendix G), the performance over different problems (Appendix H), the analysis of both prompt and completion tokens of LLMs (Appendix 1), the analysis of the number of "aha moments" during the DeepSeck-R1 reasoning (Guo et al., 2025) (Appendix J), an illustration of errors over problems (Table 7) with detailed error analysis (Appendix K), considering both the solution errors, i.e., the errors returned by npgym, and the reasoning errors, i.e., the errors produced in the internal reasoning process of LLMs, which enables the identification of the failure cases (Appendix L.).
34

---

Published in Transactions on Machine Learning Research (02/2026)
D Prompts and Responses
In this section, we carcfully design the prompt template of NPPC for LLMs to be simple, general, and consistent across different problems. The prompt template includes:
Prompts.
Problem description: where a concise definition of the NPC problem provided, including the problem name, the input, and the question be solved.
Examples: where one or multiple in context examples, defined as problem-solutinn pairs, are listed, correctness and format, for specific instances. These examples guide LLMs to generate the responses with the required format.
demonstrating the expected solutions, i.e,,
Problem to solve: target instance that requires LLMs to generate the solution.
Instruction: which provides directive to output answers in JSON format.
appc_template **.
# sproblem_nane name>> Problem Description: sproblem_deacriptan
# Examples:
Lin_context_example
# Problem to Solve:
Problem: srroblem_to_solve
# Instruction:
Now please solve the above problen. Reason step by and present your ansser in the "solution" field in the following jeon format: 'rjj
("solution"; )
...
samppleeand_solutio """Problem: exxample_problat ("solution"; <example_solution>>
35

---

Published in Transactions on Machine Learning Research (02/2026)
Responses, We extract the answers from the LLMs' responses and the code is displayed below:
def Docract_aolution_tteee wwtesioonnroo__oeee responae (response):
# find the Jaon code
match re findall (rrtaall""""" (r"..e (asoaaaa.... (a reaponse, re. r0.AOLLLL)
if not match: match re. fe..finalll (1")oon (()oos)s response, DOTALL)
if not match:
match (F response, DOTALL)
match:
json_str match[-1]
try:
remove single line comment
jaon_atz str se. "", jton_str, flage=re. MULTILINE)
# remove the multiple 1ine comment
jeon_ str re.:ub(f"/~~ dats (son.loads()sonn) ansver data(":olutionn) return answer None
"", json_atr)
except J0DaeederDeecodeerrrr KeyError, SyataxError) as e:
print (f"Errr parsing JSON or ansver field: {e}") return None, f f"Error parsing JSON answer field: {o}
else:
O"Noo JSON found in the text.*) None, "JSOX Error: No JSON found in the text."
This extraction function employs a robust, multi-stage pattern matching approach to handle various response formats. Spocifically, this function progressively relaxes format requirements through three regex patterns:
First tries find content between triple quotes with "json" marker,
If that fails, looks for "json" followed by content in curly braces,
If both fail, simply looks for any content between curly braces.
This flexible parsing template effectively handles format variations produced by different models. For instance, it accommodates models like QwQ-32B that frequently omit format prefixes or deviate from strict formatting instructions. By tolerating minor format violations, this approach ensures that evaluation focuses primarily on models' reasoning capabilities rather than their adherence to output formatting conventions. Only when all three attempts fail, the JSON error is raised, indicating genuine failure to produce feasible solution.
36

---

Published in Transactions on Machine Learning Research (02/2026)
E
List of NP-complete Problems
Problem 1.
Name: 3-Satisfiability (3SAT)
Input: A set of clauses {C1, C2.-.. .. Cm) over set of Boolean valued variables X, (21,a2,....;aa) such that cach clause depends exactly three distinct variables from X,, A clause being Boolean expression of the form yi Vj A yt where each is of the form or < (i.e. negation of æ) with being some variable in Xu. For example if n 4 and m = 3, possible instance could be the (sct of) Boolean expressions: C1 = (01 A (-r2) A (-rs)), C2 = (x2 A D3 A (-r4)), C3 = ((-w)) Ay A x.).
Question: Can each variable of X, be assigned a Boolean value a, (true, falsc) in such a way that every clause evaluates to the Boolean result true under the assignment (ri == di, E (1,...,n))?
Problem 2.
Name: Graph 3-Colourability (3-COL)
Input: An n-node undirocted graph G EV with node set V and edge set E.
Question:
Can each node G = (V, E) be assigned exactly one of three colours Red, Blue, Green in such a way that no two nodes which are joined by an edge, are assigned the same colour?
Problem 3.
Name: Clique
Input: An n-node undirected graph G = (V, E) with node set V and edge set E; a positive integer with < n.
Question: Does G contain a k-clique, i.c. subset W of the nodes V such that W has size k and for each distinct pair of nodes u, in W, {u, o) is an edge of G?
Problem 4.
Name: Vertex Cover
Input: An n-node undirected graph G (V, E) with node set V and edge set E; positive integer
k with k < n.
Question: Is there subset W of having size most & and such that for every edge {u, ta in at least one of and belongs to W?
Problem 5.
Name: Quadratic Diophantine Equations
Input: Positive integers a, b, and c.
Question: Are there two positive integers and such that (a*x**)) + (b* v) =??
Problem 6.
Name: Shortest Common Superstring
Input: A finite set R {r1, .2...., F of strings (sequences of symbols); positive integer k.
Question: there a string w of length at most such that every string in R is a substring of w, i.., for each r in RG w can be decomposed as w = worw where wo, wi are (possibly empty) strings?
Problem 7.
Name: Bandwidth
Input: n-node undirected graph G = (V, E); positive integer k S n.
Question: Is there linear ordering of V with bandwidth at most k, ie., a one-to-one function f.V 1,, ..., 1} such that for all edges u, v in G, If(u) f(v) k?
Problem 8.
Name: Maximum Leaf Spanning Tree
Input: n-node undirected graph G (V, E); positive integer < n.
Question: Does G have a spanning tree in which at least k nodes have degree 1?
Problem 9.
Name: Independent Set
Input: n-node undirected graph G (V, F)); positive integer k < n.
37

---

Published in Transactions on Machine Learning Research (02/2026)
Question: Does G' have independent set of size at least k, i.c., subset W of at least & nodes from V such that no pair of nodes in W is joined by an edge in E??
Problem 10.
Name: Hamiltonian Cycle
Input: n-node graph G = (V, R..
Question: Is there a cycle in G that visits every node in V exactly once and returns the starting node, and thus contains exactly n edge
Problem 11.
Name: Travelling Salesman
Input: A set C of n citics (c.....,G.)) positive integer distance d(i,j) for cach pair of cities (G, < i, E (t,. a positive integerB representing the maximum allowed travel distance.
Question: Is there an ordering (T (2)), T(n)) of the n cities such that the total travel distance, calculated as the sum of (i 1)) for 1 to 1, plus d(=(n),,(( n (1)), is at most B?
Problem 12.
Name: Dominating Set.
Input: An undirected graph G(V, B) with nodes; a positive integer h where k S n.
Question: Does contain a dominating set of size at most k i.e subset W V containing at most & nodes such that every node in W (i.e. in V but not in W) has at least one neighbor w in W where u, is edge in E?
Problem 13.
Name: 3-Dimensional Matching (3DM)
Input: disjoint sets X, Y, and Z, each containing exactly elements; set M of triples ((I), Vis a)) sisiiii m) such that xs is in X, yi in Y, and in Z, i.e. M is subset of X x Y x Z.
Question: Does M contain a matching, ie.. is there a subset Q of M such that [Q] = n and for all distinct pairs of triples (u, u, w) and (, in Q it holds that + x and v # y and w + x?
Problem 14.
Name: Set Splitting
Input: A finite set 8; A collection Ci...., Cm of subsets of S.
Question: Can S be partitioned into two disjoint subsets S1 and $2 such that for each set C2 it holds that C, is not a subset of S1 and C2 is not a subset Sy?
Problem 15.
Name: Set Packing
Input: A collection C (Ci,..., Cm) of finite sets; positive integer k S m.
Question: Are there k sets DI,..., Dr from the collection C such that for all and D, have no common elements?
D.
Problem 16.
Name: Exact Cover by 3-Sets (X3C)
Input: A finite set X containing exactly 3n elements; a collection C of subsets of each which contains exactly 3 elements.
Question: Does C contain exact cover for X, i.e., sub-collection of 3-element sets D (Di...., D.) such that each element of X occurs in exactly one subset in D?
Problem 17.
Name: Minimum Cover
Input: A finite set S: A collection C (C1,..., Cm) of subsets of S; a positive integer k S m.
Question: Does C contain a cover for S comprising most k subsets, i.e., a collection D (Di...., D.), where t < k, each D, is set in C, and such that every element in S belongs to at least one set in D?
Problem 18.
Name: Partition
38

---

Published in Transactions on Machine Learning Research (02/2026)
Input: Finite set A; for each element in A positive integer size s(a).
Question: Can A be partitioned into disjoint sets A and Ag in such a way that ExEA, s(a) = EuEA, s(a)?
Problem 19.
Name: Subset Sum
Input: Finite set A; for each element E A positive integer size s(a); positive integer K.
Question: Is there subset B of A such that EeEB s(a) K?
Problem 20.
Name: Minimum Sum of Squares
Input: A set A of elements; for each element E A positive integer size s(a); positive integers k S and J.
Question: Can A be partitioned into k disjoint sets AI,..., As such that Ei= s(x))² <= J?
Problem 21.
Name: Bin Packing
Input: A finite set U of m items; for each item u in U positive integer size s(u); positive integers B (bin capacity) and k where k S m.
Question: Can U be partitioned into l disjoint sets U....., Up such that the total size of the items in each subset Uj (for Sis S k) does not exceed B?
Problem 22.
Name: Hitting String
Input: Finite set (, sm) each s; being a string of n symbols over {0, 1, #}.
Question: Is there binary string 21 ......... In of length such that for each 83 S, 8j and agree in at least one position?
Problem 23.
Name: Quadratic Congruences
Input: Positive integers a, and c.
Question: Is there positive integer whose value is less than and is such that x2 mod == a, ie., the remainder when x² is divided by b is equal to a?
Problem 24.
Name: Betweenness
Input: A finite set of size n; a set of ordered triples, (a, b, c)2 of distinct elements from A.
Question: Is there a one-to-one one function, f:A A:A+ {0, 1,2, n 1} such that for each triple (a, b) in it holds that either f(a) < f(b) < f() or f(c) < f(b) < f(a)?
Problem 25.
Name: Clustering
Input: Finite set X; for each pair of elements and y in X, a positive integer distance d(z, v); positive integer B.
Question: Is there a partition of into 3 disjoint sets X1, X2, X3 with which: for each set X, (1, for all pairs x and y in X,, holds that d(a, S B?
39

---

Published in Transactions on Machine Learning Research (02/2026)
F Hyperparameters
The hyperparameters used for benchmarking are listed in Table 9. For both offline and online-deployed models, accuracy is averaged over three seeds and 30 trials per difficulty level per task. Each model is allowed up to three attempts to mitigate the impact of APT connection issues. For offine models, we follow the recommended sampling parameters from the technical reports of Deepseek-R1-ee R1-32B and QwQ-32B for vLLM deployment.
Table 9: Hyperparameters
Type
Hyperparameter
Value
seeds
42, 53, 64
sh_ss
1
Basic
trials
30
batch _szee
10
max tries
3
temperature
0.6
top_P
0.95
Offline Model
max _ox__tkens
7500
gpu
memory utilization
0.8
40

---

Published in Transactions on Machine Learning Research (02/2026)
G Full Results over Problems
In this section, we present the full results over problems, as displayed in Figure 6. For cach element in the table th x is the value of IQM and a and are the upper and lower values of the CI, respectively.
Table 10: 3SAT
2
3
6
10
QwQ-32B
0.94
00
1.00
.00
0.56
0.11
0.11
0.00
00
0.00 0.00
0.00
0.000
0.00
0.00
0.90
.00
DeepScck-R1-32h
0.83
0.52
0.32
0.19
0.13
0.02
0.00
0.00
0.00
0.00
GPT-4o-mini
0.84
0.27
0.170.10
0.08
0.02
0.00
0.00g
0.00
0.00 0.00
GPT-4o
0.94
0.518:57
0.43
0.22
0.09
0.010:03
0.010
0.00
0.00
0.00
(laude-3.-SSonnee
1.00
0.89
0.62
0.54
0.36
0.19
0.14
0.08
0.03
0.02
DeepSeek-V2. V3
0.94
0.78
0.38
0.34
0.21
0.06
0.01
0.00
0.00
0.00
DeepSeek-V3-222 V3-2503
1.00
1.00.0
0.98
0.89
0.680
0.53
0.380
0.28
33
0.12
0.08
0.03p.03
DeepSeek-Ri
1.00
1.00
0.99
0.000
0.98
0.97
0.91
0.83
0.64
6.667
0.23
0.13 0.77
ol-mini
0.920.93
0.910.97
0.92
0.818
0
0.20
0.03
0.00
0.00
0.00
o3-mini
0.93
0.82
0.720.8
0.770
0.82 0.71
0.60
0.30
0.13 0.20
0.12
Table 11: Vertex Cover
2
3
4
5
6
7
8
10
QwQ-32B
1.00
0.991.00
0.93
0.50 60
0.00g
0.000.00
0.000 0.000
0.000.00
0.00
0.00
DeepScck-R1-32B
0.91
0.92
0.81
0.52
0.03
0.07
0.02
0.00
0.00
0.00
0.00 0.00
GPT-44-mini
0.94
1.01
0.67
0.37
0.18
0.00
0.000.00
0.00g.0
0.00
0.00
0.00
GPT-4o
0.96
0.61.00000
0.88
0.78
0.60
0.01
0.08
0.00
0.00
0.00 0.00
Claude-3.7-Sonnee
1.00].00
0.97
0.97
0.900
0.530.57
0.370
0.370.50
0.26
0.140.17
0.040.07
DeepSeck-V3
0.92
0.97
0.96
0.89
0.340-43
0.140.20
0.06
0.03
0.03
0.01 0.03
DeepSeek- V3-2503
3eepSeek-33-2503
1.00]
1.00
1.00 00
0.870.90
0.28
0.37
0.270
0.09
0.09
0.01 0.00
00
00
DeepSeek-R1
1.00
1.00
00
1.00 1.00
1.00
1.00
1.00
0.91
0.77
0.77
0.41
0:33
0.180
0.13
0.06
ol-mini
0.748:73
0.77
0.78
0.91
0.58
0.31
0.13
0.13
0.08
0.02
o3-mini
0.820.90
0.890.93
0.89
0.80
0.590.70
0.520.57
0.190.27
0.
0.11
0.070.10
0.03
Table 12: Superstring
2
3
4
5
6
7
9
10
QwQ-32B
1.00].00
00
0.920.97
0.28
0.19
0.170
23
0.069.
13
0.080
13
0.019.03
0.000.00
0.00
DeepScel-R1-32B
0.580.70
0.240.40
0.16
0.120.23
0.10
17
0.030.03
0.02
0.00
0.000.00
0.000.00
GPT-4o-mini
0.320.47
0.08
0.02
0.010.03
0.00
0.01
0.00
0.01
0.00
0.000.00
GPT-4o
0.81
0.47
0.11
0.10
0.06
0.16
0.06
0.12
0.070
0.03
Claude-3.7-Sonnee
0.99..90
1.00
0.97
0.78
0.519.57
0.68
0.74
0.770
0.88
0.82
0.74 0.80
DeepSeck-V3
83
0.520.67
0.49
0.46
0.44
0.40
0-07
0.24
0.220.27
0.080.10
0.020.03
DeepSeek-
V3-2503
0.991.00
0.89
0.78
0.619.67
0.530
0.370-40
0.210
0.170.17
0. 0.260.25
0.130.17
DeepSeek-R1
1.00]-00
0.99,.00
0.940.97
0.810.90
0.80
0.619-77
0.370.50
0.310-31
0. 0.11
0.130.17
0.07
ol-mini
0.910.97
0.59
0.480.53
0.20
0.10
0.03
0.010.03
0.03
0.00
0.00
0.00
0.00
o3-mini
1.00
1.00
1.00
0.98
00
0.890.00
0.74
0.31
0.040.07
0.01
0.03
0.00
0.00
0.00
41

---

Published in Transactions on Machine Learning Research (02/2026)
Table 13: QDE
2
3
6
7
10
QwQ-32B
0.72
00
0.56
0.19
0. 0.166.05
0.03
03
0.00
0.00g
0.00
0.00
0.00
0.00
DeepSeek-R1-32B
0.84
0.620
0.11
0.08
0.00
0.00
0.00
0.00
0.00
0.00
GPT-4o-mini
0.490.33
0.23
0.03
0.000
0.00
0.00
0.00g
0.00
0.00
0.00
GPT-4o
0.670.50
0.43
0.08
0.03
0.01
0.00
0.00
0.00
0.00
0.00
Claude-3.7-Sonnet
0.96
0.97
0.78
0.59
0.10
0.00
0.00g
0.00
0.00
0.00
0.00g.00
DeepSeek-V3 V3
0.97
0.89
0.38
0.19
0.04
0.02
0.00
0.00
0.00
0.00
DeepSeek- V3-2503
-33-55e
1.00
1.00
1001.00
0.68
0.64
0.30
0.170
0.08
0.01
0.08
0.00
DeepSeek-Ri
1.00
.00
1.00
1-00
1.00
1.0
0.97
0.82
0.68
0.27
0.17
0.09
0.03
00
ol-mini
0.570.70
0.59
0.440.63
0.46
0.110
0.030
0.00
0.00
0.00
0.000:00
o3-mini
0.94
0.99
0.94
0.96
0.81
0.66
0.30
0.27
0.27
0.13
Table 14: 3DM
2
3
6
7
10
QwQ-32B
1.00
00
0.98
0.93
0.94
0.97
0.33
0.330.83
83
0.06
10
0.00
0.000.00
0.00
0.00 0.00000
0.00
DeepScek-R1-322
0.87
0.42
0.09
0.00
0.00
0.01
0-03
0.00
9.00
0.000.00
0.000.00
0.00
GPT-4o-mini
0.43
0.09
0.02
0.00g
0.00
0.00
0.00
0.00
0.00
0.00%
GPT-4o
0.640
0.24
0.13
0.10
0.02
0.00
0.00g.00
0.00
0.00
0.000
Claude-3.7-Sonnet
0.96
0.840.90
0.76
0.59
0.21
0.09
0.07
0.00
0.00
0.00
DeepSeek-V3. V3
0.74
0.320.47
0.08
0.03
0.00
0.00
0.00
0.00
0.00 0.00
DeepSeek- V3-2503
-3-22503
0.949.97
0.76
0.49
0.318.17
0.07
10
0.030.07
0.03
0.00
0.00 0.00
DeepSeek-R1
1.00].00
1.00
0.98
0.97.
0.93
0.91
0.910.97
0.57
0.27
0.02
ol-mini
0.870.93
0.89
0.810.87
0.770
0.38
0.26
0.110
0.01
0.00
0.00
o3-mini
0.63
0.86
0.72
0.710.50
0.57
0.56
00.70
0.38
0.30
0.23
0.20 0.25
Table 15: TSP
1
2
3
5
6
7
8
9
10
QwQ-32B
0.619.80
0.410.53
0.420.53
0.56g.60
0.26
0.19
0.020.07
0.00g.00
0.000
0.00
DeepSeek-R1-321
0.880.90
0.62
0.30
0.130.20
0.020.03
0.01 0.00
0.00
0.00
0.00
0.000.00
GPT-4o-mini
0.93
0.34
0.40
0.120:30
0.070.10
0.00
0.00
0.000.00
0.00
0.00
0.00
GPT-4o
0.97
0.76
0.59
0.40
0.22
0.16
2.23
0.080.0
0.02
0.00
0.00
0.07
Claude-3.7-Sonnel
1.00
0.98
0.90
0.83
9.960.90
9.90
8.8
0.540.70
0.510
0.53
0.08
0.06
10
DeepSeek-V3
0.981.00
0.90
0.74
0.620.77
0.77
0.49
0.49
0.17
0.070.13
0.020.03
0.00%
DeepSeek- V3-2503
1.00..00
0.940.97
0.96
0.830.87
0.70
0.66
0.39
0.100
0.01
0.010.03
DeepSeek-R1
1.00
0.99.000
0.970
0.99..00
0.87087
0.78
0.62
0.24
0.03
0.00
ol-mini
0.849.90
90
0.89
0.670.77
0.570
0.34
0.370.13
0.180
0.010.03
0.00
0.000.00
0.00
0.00
03-mini
0.790.8
87
0.
0.530.63
0.28
3.7
0.30
0.30
0.19
0. 17
0.07
0.07
42

---

Published in Transactions on Machine Learning Research (02/2026)
Table 16: Hamiltonian Cycle
2
3
6
7
10
QwQ-32B
0.94
000000000000
0.87
0.80
0.62
0.33
40
0.16
20
0.03
0.00
0.00
0.00
23
0.00
DeepSeek-R1-32B
0.69
0.36 00
0.24
0.09
0.00
0.01
0.02
0.00
0.00
0.00
GPT-4o-mini
0.70
0.26
0.09
0.080
0.01
0.00
0.01
0.00
0.00
0.00
GPT-4o
0.730.73
0.39
0.22
0.12
0.09
0.01
0.06
0.00
0.00
0.00
Claude-3.7-Sonnet
0.99)
0.80
0.74
0.64
0.32
0.23
0.27
0.16
0.10
0.02
DeepSeek-V3 V3
0.83
0.44
0.14
0.16
0.09 0000
0.06
0.06
0.06
0.01
0.01
DeepSeek- V3-2503
V33-25e
0.99
1.00
0.820.77
0.510
0.38
0.16
0.14
0.09
0.10
0.06
0.03
DeepSeek-Ri
1.00
1.00
0.97
0.910
0.76
0.64
0.73
0.49
0.36
0.170.23
0.04
1.00
ol-mini
0.72
0.710-77
0.540.00
0.400
0.19923
23
0.230
0.12
0.08
0.04
0.000:00
o3-mini
0.820.83
0.840.90
0.71
0.71
0.63
0.59
0.440
0.320
0.20
0.22
Table 17: Bin Packing
2
3
6
7
10
QwQ-32B
0.88
0.83
0.46
0.080.20
0.00
00
0.00%
00
0.00
0.000.00
0.00
0.00 0.00000
0.00
0.00
DeepScek-R1-221
0.26
33
0.03
0.01
0.03
0.00
0.00
0.00
0.00
0.000.00
0.00 0.000.00
GPT-4o-mini
0.30
03
0.03
0.04
0.03
0.10
0.00
0.00
0.00
0.00
0.00
0.00%
GPT-4o
0.830.73
0.440.50
0.34
0.180.2
0.04
0.02
0.00g
0.00
0.00
0.000
Claude-3.7-Sonnet
0.98
0.89
0.58
0.39
0.07
0.01
0.010.03
0.03
0.01
0.00
0.00
DeepSeek-V3. V3
0.66
0.46
0.44
0.37
0.06
0.04
0.02
0.00
0.01
0.00
0.03
0.00
DeepSeek- V3-2503
1.00
0.870:93
0.74
0.62
0.18
0.180.23
0.09
0.02
0.020.03
0.00
00
DeepSeek-R1
1.00].00
1.00
1.00
0.98
1.00
0.80
90
0.640-77
0.49
0.29
0.060-10
0.03
1.00
ol-mini
0.670.80
0.58
0.52
0.33
0.31
0.19
0.070
0.00
0.02
0.01
0.00
o3-mini
0.67 0.720.83
83
0.62
0.48
0.41
0.29
0.24
0.17
0.42
0.28
0.33
0.20
Table 18: 3-COL
2
3
5
6
7
9
10
QwQ-32B
0.961.00
0.91
0.780.87
0.56
0.34
0.10
0.018.03
0.010.03
0.000
0.00
DeepSeek-R1-322
0.49
0.51
0.03
0.010.03
0.00
0.00
0.00g
0.00
0.00 0.00
GPT-4o-mini
0.40
0.17
0.000.00
0.000.00
0.000.00
0.00
0.000.00
0.00
0.00
0.00
0.00
GPT-4o
0.60
0.39
0.53
0.030.10
0.01
0.01
0.00
0.00
0.00
0.00
0.000.00
Claude-3.7-Sonnel
0.76
87
0.70
93
0.220
0.170
0.09
0.04
0.03
0.00
0.00 0.00
DeepSeek-V3
0.670.70
0.60
0.13
0.120.17
0.030.07
0.02
0.020.07
0.00
0.000.00
0.00%
DeepSeek- V3-2503
0.80
0.90
0.48
0.640.73
0.320.37
0.16
0.16
0.090.20
0.02
0.000.00
DeepSeek-R1
0.99..00
1.00
0.97
0.970.97
0.880.93
0.93
0.72
0.720.8
0.510.07
0.22
0.04
ol-mini
0.619.70
0.76
87
0.570
0.62
0.370
0.27
0.340
0.170.23
0.07
0.03
0.029.07
03-mini
0.981.90
1.00
0.93
0.87
0.96
0.84
0.780.70
0.720.80
0.71
0.61
0.47
0.51
0.47
0.53
0.29
3030
43

---

Published in Transactions on Machine Learning Research (02/2026)
Table 19: Min Sum Square
2
3
6
7
10
QwQ-32B
0.77
80
0.00
0.00g
0.00
0.00
0.000.000
0.00
0.00
0.00
0.00
0.01
0.00
0.00
0.00
0.00
0.00
DeepSeek-R1-32B
0.230.10
0.00 .0
0.04
0.070.03
0.06
0.04
0.02
0.06
0.01 0.03
0.06
GPT-4o-mini
0.74
0.620.30
0.03
0.070.03
0.08
0.03
0.03
0.02
0.02
0.04
GPT-4o
0.94
0.82
0.46
0.56
0.44
0.48
0.04
0.001:00
0.01
0.01
0.00
Claude-3.7-Sonnet
0.98
0.84
0.83
0.736.70
80
0.79
0.64
0.59
0.67
0.62
0.14
DeepSeek-V3 V3
0.87
0.90
0.84
0.58
0.58
0.48
0.07
0.17
0.07
0.02
DeepSeek- V3-2503
V3--553
1.00
0.480.30
0.71
0.59
0.62
0.61
U.70
0.22
23
0.290
0.02
0.00
DeepSeek-Ri
1.00 00
0.88
0.64
0.460
0.470
0.39
0.13
0.13
0.07
0.020.03
ol-mini
0.62
0.70
0.270
0.180.10
0.14
0.100
13
0.030.10
0.06
0.02
0.03
o3-mini
0.69
0.38
0.38
0.39
0.52
0.30
0.440
0.24
0.03
0.18
Table 20: Bandwidth
2
3
6
7
10
QwQ-32B
0.96
0.91
0.90
00
0.840.23
0.993
0.76
87
0.66
0.63
0.30
0.20
0.06
13
DcepScek-R1-325
0.93
0.830.87
0.870.93
0.67
0.540-70
0.49
0.380
0.11 0.13
0.14
0.
0.03
GPT-4o-mini
1.00
0.94
0.94
0.840
0.78
0.470
0.46
47
0.20
0. 0.
0.03
GPT-4o
1.00
0.96
0.97
0.94].00
0.78
0.62
0.60
0.22
0.10
0.02
Claude-3.7-Sonnet
1.00 00
0.96
0.96
0.00
0.87
0.78
0.66
0.62
0.28
0.11
0.07
0.02
DeepSeek-Vä. V3
1.00
0.98
0.99
0.93
0.74
0.63
0.56
0.34
0.23
0.08
1000
DeepSeek-V3-222 V3-2503
1.00
0.93
0.89
0.62
0.58
0.570.00
0.430.3
0.330.10
0.170.20
0.04
0.04
DeepSeek-R1
1.00].00
0.90
0.93
0.880.93
0.83
0.68
0.59
0.340
0.240.30
0.07 0.03
ol-mini
0.740.80
0.740.83
0.84
0.82
0.82
0.68
0.59
0.33
0.24
0.06
o3-mini
0.80
0.88
0.82
0.90
0.93
0.72080
0.58
0.52
0.20
0.170
0.08 0.07
Table 21:
Max Leaf Span Tree
2
3
4
5
6
7
8
9
10
QwQ-32B
0.73
0.93
0.28
0.06
0.00g
0.00
0.00g
0.00g.00
0.000
0.00%
DeepSeek-R1-321
0.20
0.240-37
0.18 27
0.00g.00
0.00
0.00
0.00g.00
0.00g.00
0.00 0.00
GPT-4o-mini
0.26
0.199.40
0.010.03
0.000.00
0.00
0.00
0.000.00
0.00
0.00
0.00
0.00
GPT-4o
0.49
0.53
0.29
0.24
0.08
0.00
0.000.00
0.00
0.00
0.00
Claude-3.7-Sonnel
1.00].00
0.993
0.96
0.82
0.71
0.59
0.120
0.00
0.000 0.00
DeepSeek-V3
0.79
83
0.880.93
0.89
0.69
80
0.560.60
0.260
0.270.43
0.09
0.020.03
0.01
0.00
DeepSeek- V3-2503
0.90
0.86
0.76
0.390.4
0.180.30
0.220.27
0.280
0.170.20
0.070.33
0.020.03
DeepSeek-R1
0.970.97
0.99.
0.880.0
0.630-77
0.39
0.18
0.210
0.23
0.01
0.01
0.03
0.00
ol-mini
0.70g.73
0.530
0.570.57
0.178.20
0.02
0.020.03
0.000.00
0.00
0.000.00
0.00
0.01
0.00
0.000.00
03-mini
0.770
0.680.73
0.66
0.66
0.420.50
50
0.26
0.19
0.160
0.11
0.17
0.
44

---

Published in Transactions on Machine Learning Research (02/2026)
H
Performance over Problems
In this section, we present the performance of LLMs on cach problem across different levels.
IQM
Mean
Median
Optimality Gap
03-mini- ol-mini
DeepSeek-RL
DeepSeek-V3-25555
DeepSeek-33
Claude-3.7-Somme
GPT-4o
GPT-4o-mini
DeepSeek-R1-326
QwQ-32B
0.25 0.50 0.75
0.2
0.4
0.6
0.80.0
0.3
0.6
0.9
0.4
0.6
0.8
Figure 15: 3SAT
IQM
Mean
Median
Optimality Gap
03-mini
ol-mini DeepSeek-RI
DeepSeek-v3-2500
DeepSeek-V3
Claude-3.7-Sonme
GPT-40
GPT-4o-mini
DeepSeek-R1-32B-
QwQ-32B
0.2
0.4
0.6
0.30
0.45
0.60
0.00
0.25
0.50
0.75
0.45
0.60
0.75
Figure 16: Vertex Cover
IQM
Mean
Median
Optimality Gap
03-mini
ol-mini DeepSeek-R1
DeepSeek-V3-2500
DeepSeek
Claude-3. 3-Sonntt
GPT-4o
GPT-4o-mini DeepSeek-R1-385
QwQ-32B
0.25
0.50
0.75
0.25
0.50
0.75
0.00
0.25
0.50
0.75
0.25
0.50
0.75
1.00
Figure 17: Superstring
45

---

Published in Transactions on Machine Learning Research (02/2026)
IQM
Mean
Median
Optimality Gap
03-mini-
ol-mini
DeepSeek-R1
Deep5eek-V3-2503
III
DeepSeek-V3
Claude-3.7-Somee
GPT-4o
GPT-4o-mini
DeepSeek-R1-22
QwQ-32B
0.0
0.2
0.4
0.6
0.2
0.4
0.6
0.00
0.25
0.50
0.75
0.4
0.6
0.8
Figure 18: QDE
IQM
Mean
Median
Optimality Gap
03-mini-
o1-mini DeepSeek-R1-
DeepSeek-V3s 3eep3eee-332203
III
DeepSeek-V3
Slaude-3.7-Soneee
GPT-4o
GPT-4o-mini
DeepSeek-R1-32B
QwQ-32B
0.00
0.25 0.50
0.75
0.2
0.4
0.6
0.80.0
0.3
0.6
0.9
0.4
0.6
0.8
Figure 19: 3DM
IQM
Mean
Median
Optimality Gap
03-mini
o1-mini
DeepSeek-R1
DeepSeek-v3-2500
DeepSeek-V3
Claude-3.7 3.-oe--.--Sonett
GPT-4o
GPT-4o-mini
DeepSeek-R1-32B
QwQ-32B
0.25
0.50
0.75
0.15
0.30
0.45 0.60
0.00
0.25
0.50
0.75
0.45
0.60
0.75
Figure 20: TSP
IQM
Mean
Median
Optimality Gap
03-mini ol o1-mini-
DeepSeek-R1
DeepSeek-V3-2500
DeepSeek-V3
GPT-4o
GPT-4o-mini
DeepSeek-R1-22
QwQ-326
0.2
0.4
0.6
0.15
0.30
0.45
0.00
0.25
0.50
0.75
0.45
0.60
0.75
0.90
Figure 21: Hamiltonian Cycle
46

---

Published in Transactions on Machine Learning Research (02/2026)
IQM
Mean
Median
Optimality Gap
03-mini
ol-mini DeepSeek-R1
DeepSeek V5-25 2503
DeepSeek-V3
Claude-3.7-Sonee
II
GPT-4o
GPT-4o-mini
DeepSeek-R1-3
QwQ 32B
0.2
0.6
0.00
0.25
0.50
0.75
0.4
1.0
Figure 22: Bin Packing
IQM
Mean
Median
Optimality Gap
03-mini
ol-mini DeepSeek-R1
DeepSeek-V3-295 2502
DeepSeek-V3
Claude-3.7 S.tnnet
GPT-4o GPT-4o-mini-
DeepSeek-R1-3t
QwQ-328
0.00
0.25
0.6
0.75
0.6
Figure 23: 3-COL
IQM
Mean
Median
Optimality Gap
03-mini
ol-mini DeepSeek-R1
SeepSeek-v3-2500
DeepSeek-V3
Claude-3.7-Son
GPT-4o
GPT-4o-mini
DeepSeek-R1-
QwQ-32B
0.0
0.4
0.6
0.2
0.4
0.6
0.8
Figure 24: Min Sum Square
IQM
Mean
Median
Optimality Gap
03-mini-
o1-mini- DeepSeck-R1
DeepSeek-v3-2541
DeepSeek-V3
Claude-3.7-Sonnee
GPT-4o
GPT-4o-mini
DeepSeek-R1-328
QwQ-32B
0.0
0.4
0.15
0.30
0.45
0.2
0.4
0.6
0.60
0.75
0.90
Figure 25: Max Leaf Span Tree
47

---

Published in Transactions on Machine Learning Research (02/2026)
Mean
Median
Optimality Gap
03-mini- o1-mini DeepSeek-R1
DeepSeek-V3-295
DeepSeek-V3
Claude-3.7-Sonnee
GPT-4o
GPT-4o-mini-
DeepSeek-R1-32B
QwQ-32B
0.48
0.56 0.64
0.72
0.50
0.55
0.60
0.65
0.5
0.6
0.7
0.8
0.35
0.40
0.45
0.50
Figure 26: Bandwidth
48

---

Published in Transactions on Machine Learning Research (02/2026)
Tokens
In this section, we present the results of the prompt and completion tokens used in LLMs.
QwQQ-378
DeepSeokkRR133
Claude-3
3000
3000
Prommee
2000
2000
2000
2000
2000
1000
1000
1000
Completion
3000
$000
2000
1000
1000
2
10
3
3
2 3
DeepSeok-V3
Doep5nel-/3.5503
DeepSenk-R1
03-miri
Prompe
2000
2000
2000
2000
2000
1000
1000
1000
1000
1000
Completion
4000
20000
2000
10000
20000
10000
9 10
Figure 27: 3SAT
Dw0-328
DeepSeek-RR
GPT-4o-mini
GPT-4o
Claude-3 7-Sonnet
4000
4000
Promii
5000
5000
4000
wirrn
2500
2500
2000
0.4
0
Completion
7500
2000
2000
2500
1000
1000
9 10
6
9
Deeep-eek--V3
DeepSeek-//32550
DeepSeek-R1
61-miri
03-mini
Promipp
4000
4000
4000
4000
4000
2000
2000
2000
2000
2000
0
0
Completion
20000
40000
50000
2000
10000
20000
10
Figure 28: Vertex Cover
49

---

Published in Transactions on Machine Learning Research (02/2020)
DeepSeek-Ri
mPn-4o-mini
Claude-3.7-Sone
Proinet
50000
cerrect wrong
50000
wrogg
40000
ceneci krong
40000
amei wrmn
50000
wrrg
srrest
5500
25000
20000
20000
25000
Completion
5000
5000
5000
2000
3000
3000
2000
2500
1000
1000
9 10
9
8
90
8 10
10
DeepSeck-V3
DeepSrek-V3-2500
DeepSeekRR
03-mini
Proinet
50000
cenrect
wrong
50000
wrorg
50000
wrong
40000
wrang
40000
correct wrrng
55000
25000
25000
20000
20000
Completion
4000
4000
10000
2000
2000
10000
5000
20000
10
9 10
5
8
2
10
10
Figure 29: Superstring
QwQQ-328
DeepSeak-R1-528
GPT-4o-minl
GPT-4o
Claude-3 3.7.Sonnet
Prompp
cornect
200
connect
170
170
oeneet wrog
190
oirect
180
180
wrenz
wrogg
160
160
180
Complettion
2000
4000
2000
5000
2000
2500
4
DoepSeek-VV3
DaspSnek-v3-2503
DeepSenk-R1
61-mini
63-mini
Prompp
160
wrong
Coreect
160
wrong
contect
160
OIneect
180
wrog
165
wrog
Oerest
160
150-
150
150
170
155
Complettio
4000
4000
40000
20000
2000
10000
10000
10
Figure 30: QDE
6000
Ow/-326
6000
DeapSeek
4000
GPn-4o.min
4000
GPT-40
Claude-3, Soude-3.7-Sormet
Prompt
2000
2000
2000
2000
2000
Completion
3000
20000
5000
2000
2000
2000
1000
0
10
0
5
DeepSeek-A43
DeepSeek- 33-5033
DeepSeek-RI
0.I-mini
033mmini
4000
4000
4000
Prempt
2000
2000
2000
2000
2000
Completion
20000
40000
2000
10000
10000
2000
10
4
10
Figure 31: 3DM
50

---

Published in Transactions on Machine Learning Research (02/2020)
DeepSeek-R1
min-
Claude-3.7-Some
Promet
cerrect wrng
40000
caneci wrong
40000
cenil vemn
40000
carest worg
10000
50000
wrog
20000
20000
20000
Completion
4000
5000
5000
10000
5000
5000
10
10
8
10
6
9 10
DeepSeck-V3
DeepSeek-V3-2990
DeepSeek-R1
01-mini
03-mini
Proingt
40000
cerrect
40000
40000
40000
40000
cornect wrrrg
wrong
wror0
wrong
veang
20000
20000
20000
20000
20000
Completion
4000
4000
15000
40000
2000
2000
10000
20000
20000
5000
10
9 10
5
8
10
2
10
10
Figure 32: TSP
QwQQ-328
DeepSeak-R1-326
GPT-4o-mini
GPT-4o
Claude-3 7.Sonntet
Prompg
4000
wrong
Connect
4000
connect wrenz
OWTNT W22
wrong
oorect
2000
2000
2000
2000
2000
7500
3000
4000
Compiaation
3000
5000
2000
1800
0
DoepSeek-VV
DaspSnok-/3-2503
DaepSenk-RR
01-mini
6.-min
Promptt
COrEeCT
Contect
wrong
wronz
wrog
wrzg
2000
2000
2000
2000
2000
Conglettio
4000
4000
20000
20000
50000
2.000
2000
10000
10000
25000
10
Figure 33: Hamiltonian Cycle
Ow0-326
DeepSeek
GPT-4o-mini
GPT-40
Taude-3.7-Sornet
Prompt
1000
1000
1000
1000
1000
500
500
Completion
3000
20000
5000
2000
5000
2000
1000
1000
10
0
5
Deveg Seek-V3
DeepSeek- 332503
DeepSeek-R1
0l-mini
03-mmini
Prompt
1000
1000
1000
1000
1000
500
Completion
4000
2000
10000
20000
2000
10
4
5
Figure 34: Bin Packing
51

---

Published in Transactions on Machine Learning Research (02/2020)
DespSeck-R1-33
Claude 7-5onnet
Promet
1500
cerrecl
centci wrnnz
comest wrsng
comesi wrrng
1000
wrong
1000
500
500
500
500
500
Completin
5000
7500
5000
1500
1500
1000
3000
2000
2500
500
500
9 10
9
10
4
6
9 10
1
6
9 10
6
9 10
DespSeck-V3
DeepSeek-v3-2500
DespSeck-AR
03-mini
Congletion Promet
1000
cerrect
sron
cencel smon2
cemract We3n2
1000
compul wrrng
1000
compel wrting
500
500
500
500
500
4000
4000
15000
10000
50000
10000
25000
10
9 10
4
6
9
10
9 10
10
Figure 35: 3-COL
QwQQ-328
DeepSeak-R1-328
3000
GPT-4o-mini
3000
GPT-4o
3000
Claude-3 3.7-onnett
Prompg
3000
2000
cornect
3000
2000
wrenz
connect
2000
OMTENT
2000
erog
2000
wrzng
oorect
1000-
1000
1000
Comppettion
7500
5000
2000
3000
4000
2000
2000
2,00
1800
1000
2
3000
DoepSeekkvV3
3000
DaspSnek-v3-2503
DeepSenk-RR
3000
01-mini
3000
63-mini
Prompe
2,00
wrong
ConRect
2000
wronz
contect
2000
Weang
2000
wnog
2000
wrzgg
4000
4000
40000
Complettion
15800
2000
2000
10000
10000
20000
5000
10
Figure 36: Min Sum Square
OwO-338
DeepSSeet-R1-S R1-328
GPT-4o-mini
GPT-4o
Claude-3 7-5annet
4000
4000
Proiegp
Completion
7500
3000
5000
2500-
1000
500
1000
10
5
DeeepSeek-V3
SeepSeek- 2ee--/3---53 2503
Deeep (eek-RR
o1-mini
0.3mmni
3000
3000
pr
Completion
15000
7500
50000
10000
2000
2000
2500
25000
9 10
10
Figure 37: Max Leaf Span Tree
52

---

Published in Transactions on Machine Learning Research (02/2026)
Prompt
350
300
cornect
QwQQ-328
300
350
DeepSeak-R1-288
connect
350
300
GPT-4o-mini
350
300
oenect
GPT-4o
350
Claude 7-Sonnet
wizng
oirect
300
250
250
250
250
Compi letionation
1500
3000
3000
5000
1000
1000
2000
2500
1000
500
6
DiepSSekkvV3
DaspSnek-va-2503
DeepSank-RR1
61-mini
63-mini
350
350
350
Prommt
cortect
contect
Derrect
350
wrzng
correct
300
wrzng
correct
300
250
250
250
250
4000
4000
Complettio
40000
10000
2000
2000
20000
10
Figure 38: Bandwidth
53

---

Published in Transactions on Machine Learning Research (02/2026)
J
Aha Moments
This section investigates the phenomenon of "aha moments", sudden bursts of insight that shift reasoning strategies, happened in DeepSeek-RI, which are usually marked by linguistie cues, e.g. "Wait, wait. That's an aha moment T can flag here.". The "aha moments" occur when models abruptly recognize the flawed logic, which align with the creative restructuring human cognition for self-correction. Figure 39 display the number of "aha moments' in DeepSock-R1 across different NPC problems, where the blue and the red dots represent correct and wrong outputs respectively.
3SAT
Vertex Cover
Superstring
QDE
80
60
40
20
0
1
3
5
6
8
10
1
3
5
7
10
1
3
5
7
9
10
3
5
7
9
10
3DM
TSP
Hamiltonian Cycle
Bin Packing
80
60
20
0
1
3
4
5
6
7
8
10
1
3
5
7
8
9
10
1
3
5
7
9
10
2
3
5
7
9
10
3-COL
Min Sum Square
Bandwidth
Max
Leaf Span Tree
80
60
40
20
1
3
5
6
10
1
3
5
7
9
10
1
3
5
7
9
10
5
7
9
10
Figure 39: Number of aha moments in DeepSeck R1
54

---

Published in Transactions on Machine Learning Research (02/2026)
K
Solution Errors
This section visualize the solution errors of different LLMs on the 12 core NPC problems, revealing variations in error distribution across models and difficulty levels. Por each problem, each color corresponds to a specific error type as listed in Table 7.
QwQ-328
DeepSeek-R1-322
GPT-4o-min
GPT-4o
Claude-3 3-5oneett
100
1
1
DeepSeek-V3
V3e
DeepSeek
100
50
4
6
10
4
7
10
3
8
10
4
3
5
7
10
JSON ERROR
VERIFICATION ERROR
3SAT ERROR
3SAT ERROR 2
Figure 40: 3SAT
QwQ-328
DeepSeek<R1 R1-32B
GPT-4o-mini
GPT-4p
Claude 3.7-Sonnel
100
50
90
5
9 10
10
9 10
6
91
DeepSeek-V3
DeepSeek-V3-2503
DeepSeek-R1
ol-mini
03-mini
100
3
123
2
5
JSON ERROR VERIFICATION ERROR
VERTEX COVER ERROR 1 VERTEX COVER ERROR 2
VERTEX COVER ERROR
VERTEX COVER ERROR
Figure 41: Vertex Cover
QwQ-32B
DeepSeek R1-328
GPT-4o-min mini
GPT-4e
Claude-3 3.u 3.7-Sonnet
100
50
6
9
10
5
10
12343
8 10
2
9 10
90
SVe
DeepSeek 23-3
DeepSeek-R3
o1-mini
03-mini
100
50
90
1
Figure 42: Superstring
55

---

Published in Transactions on Machine Learning Research (02/2026)
QwQ-32B
DeepSeek-R1-328
GPT-to-mini
GPT-4o
100
DeepSeek<V3
DeepSeek-V3-
100
50
4
6
10
2
5
7 90
1
6 8 10
1
6
90
5
7
10
JSON ERROR
QDE ERROR
QDE ERROR
QDE ERROR 3
VERIFICATION ERROR
Figure 43: QDE
OwQ-328
DeepSeek-R1-328
GPT-4o-mini
GPT-4o
Caude-3.7-Sonnet
50
4
6
8
90
2
3
4
5
7
10
2
3
5
6
8
10
2
3
4
6
8
9
10
2
5
10
SeepSeek.V3
DeepSeek MMpSSenk-V3-2503
2503
DeepSeek-R1
ol-mini
03-mini
50
2
4
6
8
9
10
3
5
7
9
10
1
2
3
6
8
9
10
2
4
6
8
9
10
2
3
5
9
10
JSON ERROR
3DM ERROR
3DM ERROR
3DM ERROR
VERIFICATION ERROR
Figure 44: 3DM
QwQ-32B
DeepSeek-R1 R1-328
GPT-4o-mini
GPT-4o
Claude-3.7
Laade-3.7-Sonnet 7-Sonnet
100
50
10
10
10
2
9
V3
DeepSeek 2503
DeepSeek
o1 mini
03-mini
100
50
9
90
JSON ERROR
TSP ERROR
TSP ERROR
TSP ERROR
VERIFICATION ERROR
TSP ERROR
Figure 45: TSP
56

---

Published in Transactions on Machine Learning Research (02/2026)
OwQ-32B
DeepSeek-R1es ---338
GPT-4o-mini
GPT-4o
Claude-3.7 3.7-Sonnet
50
2
4 6 8
9
3
4
5
7
90
1 2
6
9 10
2
4
9
10
3
5
7
8
DeepSeek-V3
DeepSeek-V3-2003
DeepSeek-R1
01-mini
03-mini
100
50
2
4
6
9
10
3
5
9
10
2
6 8 10
1 3
9 10
2
3
5
9
10
JSON
VERIFICATION
Figure 46: Hamiltonian Cycle
QwQ-328
DeepSeek-RR R1-328
GPT-4o-mini
GPT-4o
Claude-3. Paude-3.7-Sonnel
100
50
10
10
10
VeepSeek-V3
DeepSeek-V3-2500
DeepSeek-R1
100
JSON ERROR VERIFICATION ERROR
BIN PACKING ERROR
BIN PACKING ERROR
BIN PACKING ERROR 3
Figure 47: Bin Packing
QwQ-32B
DeepSeek-R1-328
GPT-4o-minl
Claude-3.7-Some
100
50
3
6
9 10
2
5
7
90
1234
8
10
4
3
5
7
10
DeepSeek-V3
DeepSeek- 2503
DeepSeek-R1
01-mini
03-mini
50
2
6
6
9
10
2
3
5
9
10
1
2
3
5
6
8
10
2
3
4
6
10
3
5
9
10
JSON ERROR
VERIFICATION ERROR
3-COL ERROR
Figure 48: 3-COL
57

---

Published in Transactions on Machine Learning Research (02/2026)
QwQ-32B
DeepSeek-R1-328
GPT-to-mini
GPT-4o
Claude-3 3-Soonee
100
DeepSeek<V3
DeepSeek-R1
100
50
2
4
6
9
10
2
5
7
9 10
3
6 8 10
3
9 10
5 7 10
JSON ERROR
MIN SUM SQ ERROR
MIN SUM SQ ERROR
MIN SUM SQ ERROR
VERIFICATION ERROR
Figure 49: Min Sum Square
OwQ-328
DeepSeek-R1-328
GPT-4o-mini
GPT-4o
Caude-3.7-Sonnet
50
2
4
6
8 90
123
3
4
5
7
10
2
3
6
8
10
2
3
6
9 10
5
7
10
SeepSeek-V3
DeepSeek
V3-2533
2503
DeepSeek-R1
ol-mini
03-mini
100
50
2
4
6
8
9
10
2
3
5
7
9
10
1
2
8
9
10
2
3
4
6
9
10
123
3
5
7
9
10
JSON ERROR
MLST ERROR
MLST ERROR
MLST ERROR
VERIFICATION ERROR
MLST ERROR
MLST ERROR
Figure 50: Max Leaf Span Tree
QwQ-32B
DeepSeek R1-322
GPT-4o-mini
GPT-4o
(aaude3.7-Sonmet 7-Sonnet
100
50
9
10
8 10
9 10
90
V3
DeepSeek 23-3
DeepSeek
0l-mini
03-mini
100
50
ERROR VERIFICATION ERROR
BANDWIDTH ERROR
BANDWIDTH ERROR
BANDWIDTH ERROR
Figure 51: Bandwidth
58

---

Published in Transactions on Machine Learning Research (02/2026)
L Analysis of Reasoning Failure Cases
DeepScck-R1. Taking Deepscek-R1 as an example, the reasoning content of its failure cases shows several patterns that lead to wrong answers. The concrete examples of failure cases for DeepSeek-RI. are shown in Table 22. Specifically, the typical reasoning failure cases include:
Cascading assumptions and placcholdor/guess: Generally, DeepSock-Ri R1 adopts the trail-and-crror approach find the answer. Although it may give the high-level approach in the beginning, after the first answer is not correct, it will start making assumptions to derive answer without logical deduction. The following verification may not consider all the given conditions; thus, the verification and the answer wrong. If it has already made multiple assumptions and verifications without deriving the correct answer, it will return placeholder or an educated guess.
Manual computations crrors and complexity avoidance: DeepScck-R1 makes manual computations that are time-cousuming and token-consuminng instead using programming, such as manually counting the length and sum of an array by listing the elements one by one. There are also computation errors that the counting, summation, sorting results are wrong. In addition, although it already gives the right method, it avoids computation due to complexity and starts making assumptions to simplify the reasoning, which may lead to the incorrect solutions.
Reliance on prompt examples: There are examples with the same requirement in the prompt, and DecpSeck-R1 analyzes and generates the answer hcavily relying on the example solution, which can be a distraction that DeepSeek-R1 wastes time verifying and editing the example solution. Reasoning repetition: The same assumption, logie, or example can be repeated multiple times without. making further progress in solving the problem, which waste of time and tokens.
59

---

Published in Transactions on Machine Learning Research (02/2026)
Table 22: Detailed Analysis with Examples of Failure Cases for DeepSeek-RI.
Detailed Failure Reason
Reasoning Content
Alternatively, perhaps the solution includes nodes 8, 2, 3, 6, 7, 9. 10, 12, 13,
14, 18, 19, 20, 22, 24, 25, 30, 34, 35, 37. Let's 's count these. That's 20 nodes.
Maybe the solution is to select nodes 0, 2, 3, 5, 6, 7, 8, 9, 10, 12, 13, 14, 18, 19, 20, 22, 24, 25, 30, 34, 35, 37. Wait, but that's 's more than 20, Need to pick 20. Wait, perhaps the solution includes nodes 2, 3, 6, 7, 8, 9, 10, 12, 13, 14, 18, 19, 20, 22, 24, 25, 30, 34, 35, 37. Let's check:
cascading assumptions
At this point, I'm not sure. Given the time I've spent and the complexity, perhaps the solution is the string jyyojamy peetdb with length 20, even though some required substrings might be missing. But according to the problem statement, there a solution. So I'll have take a guess. ... But given the time I' I've spent and the need to provide an answer, I'll make an educated guess...
placcholder/guess
Now, let's count the number of elements. Each comma separates elements. So between each number there's a comma. Let's count. commas. But maybe it's easier to split by each element. Let's do that step by step. Start from the first. element: 1. 1; 2. 14; 3. 1; 4. 1; 5. 5; ... So there are 80 items.
manual computation errors
So, if a node is in an edge that's not covered by any other node, then that node must be in the vertex cover. But checking that for each edge would be time-consuming. Let's look for edges that have a unique node, For example, if there's an edge (a, b), and neither a nor are connected to any other nodes, then one of them must be in the cover. But in graph of 40 nodes, this is unlikely. So probably most nodes have multiple edges.
complexity avoidance
Wait, in the example problem, the solution included nodes 0, 2, 4, 5, 6, 7, 8, 9, 13, 14, 15, 19, 20, 23, 25, 26, 30, 32, 34, 37. So maybe similar patterns here. But the new problem's edges are different.
Alternatively, perhaps the solution is similar to the example. The example's solution includes nodes O,
2, 4, 5, 6, 7, 8, 9, 13, 14, 15, 19, 20, 23, 25, 26, 30, 32, 34, 37. Looking at the problem's 's edge set, perhaps some of these nodes are also high-degree here. Let's see. ... Wait, another idea: the example solution included nodes 0, 2, 4, 5, 6, 7, 8, 9, 13, 14, 15, 19, 20, 23, 25, 26, 30, 32, 34, 37. If look at these nodes, perhaps they are all the nodes from one side of a bipartition. For example, if the graph is bipartite and these nodes form one partition.
reliance on prompt examples
Looking at the edges, let's see which nodes are involved a lot. For example, node 8 appears in edges like (8,18), (8,35), (8,21), (8,30), (8,39), etc. Maybe node 8 a hub. ... In the problem solve, node is involved in many edges, as per the edges provided.
reasoning repetition (example)
including 8 in the cover would cover a lot edges. For example, node 8 appears in lot of edges. Including node 8 would cover many edges. For example, many edges involve node 8. So including node 8 a must.
So perhaps the key is to find the longest possible superstring that includes as many of these as possible, then add the "b' and the other small strings. But the 'b' a problem. Let's think: the superstring must include 'b' as substring. Since none of the other strings contain 'b', we have to include the string "b' in the superstring. So the superstring will have the 'h' as standalone. But how? ... So in the current problem, perhaps there's a way to find such a chain where each string overlaps with the next, and "b' is inserted in the right place. But I'm stuck. Let's try to look for possible overlaps between the strings, especially lly those that include 'mmy' and 'b'. Wait, the 'b' must be present. How can "b' be included? Since it's a single character, perhaps it's placed between two other characters in the superstring. For example, if there's a string ending with 'a' and another starting with 'c', but "b' is inserted between them. But in this case, the other strings don't have 'a' 'c' next to 'b', so the 'b' would have to be standalone. So the superstring must contain 'b' as a separate character. ... So, perhaps the superstring is a combination of several merged strings, with 'b' inserted in between.
reasoning repetition (logic)
60

---

Published in Transactions on Machine Learning Research (02/2026)
Claude. Unlike Deepscek-R1, Claude's failure cases' reasoning content is generally much shorter. Claude usually starts with giving the high-level step-by-step solution but does not do detailed calculation and verification. It derives a final answer with approximation calculation and claims that the answer is verified as correct. An example is shown in Table 23.
Table 23: Claude Failure Case.
Based on my analysis of the edge patterns, the following nodes would form effective vertex cover:
11 (connects to many nodes)
14 (high degree, covers many edges)
10 (connects to multiple nodes)
16 (appears frequently in edge list)
(connects to several nodes)
This selection ensures that every edge in the graph has at least one endpoint in our subset, with total of 11 nodes which meets constraint.
61

---

Published in Transactions on Machine Learning Research (02/2026)
M Thorough Error Analysis of QwQ-32B
We present detailed analysis of QwQ-32B's 2 distinctive output behavior and failure modes. Table 24 provides represenlative examples of the model's reasoning outputs.
Format-Following Difficulty. notable limitation of QwQ-32B is its difficulty adhering to strict output formats. Although the prompt explicitly specifies responses in the format jsont"solu:oon" ...3, the model frequently omits the json prefix, producing outputs of the form ("solution": ...J instead. This behavior likely stems from QwQ's pretraining on mathematical problem-solving datasets, where instructions typically encourage responses such as 'Please reason step by step and place your final answer within \boxed(), rather than enforcing rigid structured formats. While the model occasionally self-corrects to conform to the specified format, such instances are rare. To address this limitation, we relax format requirements for all models in nipeval during parsing the solutions (shown in the response part of Appendix D), accopting responses of the form {"solution": ...J. This adjustment enables fairer evaluation of oflline models with limited format-following capabilities, allowing answers with minor format violations to be considered valid.
Does Increasing Token Limit Reduce Errors? For offiine models, the output token limit is set 7,500 lokens, consistent with other benchmarks (Lin et al., 2025). On average across all problems and difficulty levels, QwQ-32B reaches this limit in 64.53% of cases, demonstrating its tendency toward verbose generation. We tested QwQ-32B with an increased token limit 768), which did not significantly improve overall reasoning success rates. In contrast, other offline reasoning models such as DeepSeck-R1-4e -R-332BB do not exhibit comparable difficulties under similar conditions. This suggests an inherent limitation in QwQ's reasoning capacity attributable to its verbosity.
Limited Reasoning Capability. As shown in Appendix K, QwQ-32B exhibits distinct error distribution compared to other models, with notably high rates of JSON FRROR, particularly as problem difficulty increases. Importantly, this elevated error rate does not result from format-following issues but rather from the model's failure to complete its reasoning process and produce valid answer before reaching the token limit. We identify two common failure modes on challenging problems. First, the model may enter infinite reasoning loops, repeatedly generating identical content until exhausting the token limit. This behavior is not unique QwQ-32B and has been observed in other reasoning models, including DeepSeek-RL. illustrated in Table 22. This phenomenon highlights potential direction for future improvements in reasoning model design. Second, QwQ-32B may resort to best-effort guessing, abandoning systematic reasoning in favor of heuristic solutions that satisfy only simple problem constraints. This behavior further indicates that benchmark problems exceed the model's elfective reasoning capacity.
Takeaways for Errors of QwQ-32B
The format \boxed{} format is handled through our general answer- sewer-parsing template
The errors primarily arise from incomplete reasoning processes, driven by QwQ-32B's verbosity and limited reasoning capability
62

---

Published in Transactions on Machine Learning Research (02/2026)
Table 24: QwQ-32B Reasoning Representative Examples
Example
Reasoning Content
Problem in Format Follow-
All are present. So this should be valid solution. Let me confirm again. Another check: For X=5, we chose triple8 (5, (3,13. 'Tha uses Y=13 and Z=29 ... So correct. Yes, this seems work. So the solution the list of these triples: { ("solution': [[0.10.21][1115,28]]] 12116,2))
ing
[5,13,29] (7.18,
Self-Correction in Format Following
(6, 13, 20,.199911111 11,61, Final Answer {'solution': [3,19 66, (,,02,,, 16, (6,
Wait, the user's instruction says to present the answer in the specified JSON format. think the correct way is to just output the JSON without any extra text. So the final answer is: json
Answer json { ('solution'. 'solutionn' (6,11,.1),,6.13320)) (9,1,,2), Final
Infinite Reasoning Loop
... All present. So this is valid solution. The solution is the list of these triples. Final Answer {'solution': Final Answer ('solution':
[3,10,26] [,,18,27] [5,4,23]. [6,11,25] [7.15244)....I [6.11.25
[0.13.29 29 [1.12,28] [2,1720), [8,10,26] [4.18,,), [4,11,,,77,,,11,,,88 [3,14,33].....] Final Answer ('so-
lution': : [0,13,29] [1,12,28) ... (repeated output continues)
Best-Effort Guess
Plausible Solution: Given the complexity, I'll generate a solution by making educated guesses and ensuring key clauses are satisfied. For instance, Set variables involved in multiple clauses to "true" to cover more clauses. After careful consideration and ensuring no immediate contradictions, here's a generated solution ... For an exact answer, SAT solver should be used.
63


Reviews:
[{"review_id": "8pEAbQxvP9", "reviewer": "Reviewer_GmXh", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "Paper introduce a novel NPPC benchmarking framework to evaluate the LLM's reasoning capabilities. It involves three modules: npgym, npsolver, and npeval targeting problem generation, verification, and analysis of the performance tools, respectively. \n\nThe idea is to draw problems from the class of NP-complete problems, which are difficult to solve but easy to verify, and evaluate the performance of LLMs over these problems for reasoning. NP-complete class properties are exploited to generate problems with increasing \"complexities\" by a two-stage method: manual configuration by experts followed by empirical calibration. \n\nMy main concern is about the way difficulty levels are constructed. Once mathematical complexity of the problems is identified, the calibration step seems cyclic. Calibration decides problems as \"difficult\" if they lower the LLMs performance. The final conclusion then says that as the difficulty levels increase, LLMs performance decreases.", "claims_and_evidence_yn": "No", "claims_explanation": "The logic of difficulty Vs performance seems circular. There should be comparison with the results with computational complexity (step I (theoretically hard assigned by experts)) Vs LLMs performance, with the current plots of difficulty levels (step I (theoretically hard assigned by experts) + II (LLM calibration)). In the current settings, the plots seem redundant as the problems are labelled difficult by that same performance condition.", "audience_yn": "Yes", "audience_explanation": "The topic of benchmarking is of interest to many in the field as reasoning models are becoming increasingly important and there is a need of benchmarking frameworks that can scale indefinitely. But, the logic of difficulty notion defined in the paper needs more clarification.", "requested_changes": "The notion of \"difficulty levels\" needs to be justified for its circular logic, experiments with \"mathematical difficulty levels\" Vs performance should be considered. (critical)\n\nThere are typos in the paper (such as Laderboard Vs leaderboard, etc.) (minor)", "broader_impact_concerns": "No broader impact concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "oMaZng3LuH", "reviewer": "Reviewer_gQLy", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "**Sumary**\n\nThe paper introduces the Nondeterministic Polynomial-time Problem Challenge (NPPC), a new benchmark designed to evaluate the reasoning capabilities of LLMs. The authors argue that existing benchmarks suffer from saturation (crushing) or contamination (hacking), resulting in several models achieving very high performance in a short period after the benchmarks are released. To address this, the authors define ever-scalingness, four dimensions for the building of an effective benchmark: (i) complexity, adjustable and increasing difficulty, (ii) instances, infinite generation of evaluation samples, (iii) oversight, fast verification of the predictions, (iv) coverage, inclusion of diverse domains. To this end, the NPPC framework is compiled, comprising 25 NP-complete problems (12 core, 13 extension) that cover the aforementioned requirements. NPPC framework is implemented via: (i) npgym, which generates instances and verifies the model predictions, ii) npsolver, which provides a standardized pipeline for prompting and output parsing of various models, and iii) npeval, which systematically evaluates the performances of LLMs using various metrics (e.g. mean, IQM) and on various aspects (e.g. token usage, aha moment counts, and error types). Several contemporary offline and online models are evaluated, highlighting that the proposed benchmark is far from saturation, with the best models achieving an accuracy of less than 10%, and performance degrading with an increase in difficulty.\n\n**Strengths**\n\n* The contribution of the paper is significant. The NPPC is an evidently scalable benchmark that comprises many NPC problems, which are naturally of increasing complexity and have an infinite pool of instances. Additionally, the difficulty of the problems can be further increased, making it a long-lasting benchmark and an excellent resource for future research. Hence, it is of great value for the research community working on reasoning-related problems, a very contemporary topic.\n* The definition of the ever-scalingness is sound and interesting. All four dimensions are deemed necessary for building an effective benchmark that cannot (or at least it is hard to) be saturated, and also reflect real-world reasoning.\n* The framework implementation is technically rigorous, thorough, and will be fully open-sourced. The three components (npgym, npsolver, npeval) are well designed, and their functionality is clear. The automatic generation and verification of the npgym is clear, the prompting and completion of the npsolver is straightforward, and the evaluation protocol of the npeval covers various performance aspects.\n* An extensive experimental study is provided based on 10 recent LLM models. The models are used either directly offline or via their online APIs, and reasoning and non-reasoning LLMs are evaluated. Also, an insightful analysis of performance is provided, breaking down the types of errors made by the models, the number of output tokens, as well as the aha moments of DeepSeek-R1.\n\n**Weaknesses**\n\nAll weaknesses stated below focus on clarity and presentation of the paper.\n1. The coverage dimension of the dataset is not sufficiently discussed. Although the other three dimensions are well covered due to the nature of NPC problems, it is very clear how and why high performance on such tasks translates to real-world reasoning. Especially, the high difficulty regime might result in artificial problems with limited practical application. Addressing such concerns would strengthen the paper's motivation, and the benchmark would reach a broader audience.\n\n2. It is not very clear how the aha moments are defined, how they are quantified, and what they capture. Several references to them appear throughout the paper without a proper introduction. Additionally, there is no discussion of the results, and it is unclear what the outcome of such an analysis is. In Figure 36, the aha moments seem to be relatively uniform without following a particular pattern. In the same spirit, the importance of the number of output tokens is not justified early in the paper; however, its quantification is straightforward, and its impact is adequately discussed.\n\n3. Could the tool usage by models be a game-changer for this benchmark? There is relevant discussion in the paper, but it is unclear whether LLMs that have access to specialized solvers (or even code execution) for the particular problems can easily exploit them to solve the tasks. Although this may not be deemed as actual reasoning, it can be a way to hack the benchmark.\n\n4. The definition of difficulty needs to be better clarified. There is a distinction between \"Computational Hardness\" and \"LLM Hardness\", and it is not clear how well they are aligned. While the authors acknowledge that \"The difficulty experienced by traditional symbolic solvers does not necessarily translate to difficulty for LLMs\", the paper would benefit from a closer discussion on why the specific parameters were chosen for each problem. It appears that the hardness for LLMs comes from context length and variable tracking rather than combinatorial explosion in the traditional sense. Moreover, it is mentioned that \" the difficulty levels are further calibrated through systematic empirical testing with state-of-the-art LLMs\". Could this introduce bias against the models used for calibration, thereby giving future models an unintended advantage over the current ones?\n\n5. Although the paper contains extensive implementation details, it lacks a dedicated section that consolidates them in an accessible manner. As a result, readers do not have a reference point for locating specific information, since these details are sparsely presented throughout the paper. For example, the compared models are categorized into reasoning vs. non-reasoning and offline vs. online, which can be difficult to follow for readers unfamiliar with these distinctions.\n\n6. Some models have issues with the JSON formatting, raising corresponding errors. It is unclear whether this high failure rate is due to reasoning failure or simply an inability to follow the JSON schema.", "claims_and_evidence_yn": "Yes", "claims_explanation": "The main claim is that the proposed benchmark is far from saturation, which is effectively demonstrated by evaluating 10 widely used LLMs that performed poorly in high difficulty settings. Also, the importance of ever-scalingness is convincing and is adequately satisfied by the proposed benchmark.", "audience_yn": "Yes", "audience_explanation": "Researchers working in the field of reasoning and evaluation of LLMs will greatly benefit from the proposed benchmark.", "requested_changes": "All suggestions below would strengthen the work in the reviewer's view:\n\n1. Better motivation for the coverage aspect of the benchmark. An extension of the existing segment in the introduction (or even a new paragraph) would suffice.\n2. Introduction of the aha moments in an early stage of the paper. Discussion of the results, if there is any useful conclusion. Otherwise, consider removing the corresponding results altogether, as they are only with a single model. This would reduce clutter in the presentation and improve clarity. Additionally, it would be more beneficial to focus on analyzing the different error types and provide a more in-depth discussion about what they represent.\n3. A small-scale ablation with some models with tool usage would address such concerns. Otherwise, some relevant discussion could be added in the corresponding segment.\n4. A more detailed explanation of the chosen parameters would help clarify how they correspond to different levels of difficulty.\n5. A brief summary in the main paper (or a table/figure) of the evaluation protocol would address the sparsity of the implementation details. For example, a paragraph in the results (Section 5) that includes the core details, such as the number of instances per problem, and provides references to the relevant sections in the Appendix would resolve the issue. Also, including a table that summarizes the compared LLMs and their types, in the context of reasoning/non-reasoning, offline/online, or any other categorization, would also improve clarity.\n6. A small-scale ablation of the different prompt templates would address the formatting issue. Such ablation could be focused solely on the LLMs that exhibit these issues.\n7. Some very minor suggestions regarding visuals in the paper, for better consistency and clarity: \n    * Figure 6: Although visually appealing, it reiterates the same information shown in Figure 5. Is there anything new that can be derived from this plot?\n    * Figure 5: Some notation in the plot's caption to distinguish reasoning/non-reasoning and offline/online would help.\n    * Figure 7: Indicating whether each metric is \"higher is better\" or \"lower is better\" would make the comparison more accessible. A simple arrow next to each metric name could be sufficient. Additionally, adding borders or clearer separation between the plots would help distinguish them visually.\n    * Figure 8, 9: For clarity and visual consistency, it would be preferable to be top-aligned.", "broader_impact_concerns": "No Broader Impact Statement is provided. Some topics that could/should be discussed are the following:\n1. Compute and environmental cost. The large-scale evaluations encouraged by NPPC may increase consumption requirements, especially as the difficulty increases. Therefore, access to significant computational resources is necessary, which may have an environmental impact.\n2. Overemphasis on synthetic NPC tasks. Models may be trained to overfit NPPC, potentially diverting attention from real-world robustness and safety issues.\n3. Risk of benchmark misinterpretation. High NPPC scores could be misconstrued as general reasoning capabilities.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "x695sqI21H", "reviewer": "Reviewer_JPDw", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper introduces the Nondeterministic Polynomial-time Problem Challenge (NPPC), a reasoning benchmark designed to address the rapid saturation and potential data contamination of existing LLM benchmarks. NPPC is a benchmark that can scale over complexity, instance, oversight, and coverage to ensure continuous differentiation among LLMs over extended periods, identifying fundamental limitations for further improvement. The benchmark leverages 25 NP-complete (NPC) problems (e.g., 3SAT, Vertex Cover, 3DM) to generate procedurally verifiable instances of arbitrary difficulty. Three components, including npgym, npsolver, and npeval are designed for problem generation, unified model interaction, and statistical evaluation, respectively. Extensive experiments over widely-used LLMs demonstrate that NPPC can reduce model accuracy to below 10% at high difficulty levels, validating its resistance to saturation.\n\n### Strengths\n1. The benchmark utilizes the unique properties of NP-complete problems—specifically that they are computationally hard to solve but easy to verify to create an ever-scaling benchmark. This ensures the benchmark can scale indefinitely in complexity without requiring human curation.\n2. The framework, comprising three modules (npgym, npsolver, npeval), offers a complete pipeline for generation, interaction, and rigorous statistical analysis. Meanwhile, the framework supports both online (API-based) and offline (locally deployed) models, facilitating broad comparisons between proprietary and open-weights models.\n3. Extensive experiments and in-depth analysis verify that NPPC is a ever-scaling benchmark for reliable and rigorous evaluation of the reasoning limits of LLMs.\n\n### Weaknesses\n1. The evaluation protocol strictly requires responses in a specific JSON format. The analysis reveals that for some models (e.g., QwQ-32B), \"JSON ERROR\" dominates the failure modes, meaning the model might have reasoned correctly but failed the format check. This obscures the true reasoning capability of the models. A reasoning benchmark should isolate reasoning ability; strict formatting penalties introduce confounding variables, especially for smaller or offline models\n2. The prompt template is rigid regarding the output format, and while offline models have defined parameters (Table 8), the lack of a \"retry\" mechanism or flexible parsing for syntax errors (beyond basic regex) limits the fairness of the comparison.\n3. The authors claim \"scaling over coverage\" ensures relevance to real-world problems. While NPC problems are theoretically foundational, the paper does not empirically demonstrate that improving on abstract 3SAT or Hamiltonian Cycle tasks correlates with performance on practical downstream tasks.", "claims_and_evidence_yn": "Yes", "claims_explanation": "The submission is distinguished by an accurate and robust theoretical foundation, leveraging the definition of NPC problems, specifically their property of being computationally hard to solve but easy to verify, to logically support its framework for scalable oversight and complexity. The efficacy of the authors' two-stage difficulty calibration, which combines expert configuration with empirical validation, is convincingly evidenced by the monotonic degradation of model performance observed in the results, ensuring generated instances accurately reflect increasing complexity. Furthermore, the claim of the benchmark's \"uncrushable\" nature is supported by clear experimental data showing a consistent performance collapse across all tested models, including state-of-the-art reasoning models, as difficulty scales. Finally, the analysis offers granular insights into model behavior through clear evidence regarding token consumption and \"aha moments,\" visualizing distinct trends during inference.", "audience_yn": "Yes", "audience_explanation": "The paper addresses the critical issues of benchmark saturation and potential data contamination by introducing the Nondeterministic Polynomial-time Problem Challenge (NPPC), an ever-scaling framework that utilizes procedurally generated NPC problems to resist obsolescence. The submission offers relevant empirical data through a rigorous evaluation of state-of-the-art reasoning models, including DeepSeek-R1, Claude-3.7-Sonnet, and o1/o3-mini, identifying performance limits that current static benchmarks fail to capture. Furthermore, the work provides novel methodological contributions regarding scalable oversight, leveraging the \"hard to solve, easy to verify\" property of NPC problems, and delivers deep insights into inference-time compute behaviors, such as token usage and \"aha moments\". Finally, the detailed taxonomy of reasoning failures offers actionable feedback crucial for researchers aiming to advance model architectures and training strategies.", "requested_changes": "1. (Major) The current evaluation protocol conflates reasoning capabilities with instruction-following strictness. Implement a more robust parsing mechanism (e.g., using an LLM-based extraction step for malformed JSON or more permissive regex) to separate reasoning accuracy from formatting adherence. Alternatively, report \"Reasoning Accuracy\" (manual/soft-check) and \"Format Compliance\" as separate metrics to provide a fairer assessment of offline models like QwQ-32B.\n2. (Minor) Include a correlation analysis comparing model performance on NPPC against established applied benchmarks. This would empirically validate the claim that \"coverage\" of NPC problems translates to \"practical value\" and \"downstream tasks\" as argued in the introduction.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Decision: Accept (poster)