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

Chang Yang* 1, Ruiyu Wang* 2,
Junzhe Jiang1, Qi Jiang3, Qinggang Zhang1, Yanchen Deng4, Shuxin Li4, Shuyue Hu5,
Bo Li1, Florian T. Pokorny2, Xiao Huang1, Xinrun Wang† 6

1The Hong Kong Polytechnic University, 2KTH Royal Institute of Technology,
3Carnegie Mellon University, 4Nanyang Technological University,
5Shanghai AI Lab, 6Singapore Management University
*Equal contribution, †Corresponding author

🎉 News


[2025-05-06] Leaderboard is on!

[2025-04-15] We introduce NPPC, an ever-scaling reasoning benchmark for LLMs!

🏆 Leaderboard

Search:

Select Columns to Display:

Model Filter:

Open-Source?

Reasoning?

Model↕
Rank↕
Average↕
Date↕
3SAT↕
Vertex Cover↕
Superstring↕
QDE↕
3DM↕
TSP↕
Hamiltonian Cycle↕
Bin Packing↕
3-COL↕
Min Sum Square↕
Bandwidth↕
Max Leaf Span Tree↕
Open-source↕
Reasoning↕
Link

DeepSeek-R1

1

0.62

2025-01

0.77

0.65

0.61

0.6

0.76

0.65

0.63

0.63

0.7

0.42

0.65

0.43

open-source

reasoning

🔗

o3-mini

2

0.51

2025-01

0.59

0.5

0.5

0.63

0.52

0.35

0.55

0.43

0.73

0.36

0.57

0.4

proprietary

reasoning

🔗

Claude-3.7-Sonnet

3

0.49

2025-02

0.39

0.55

0.79

0.34

0.35

0.66

0.43

0.3

0.2

0.68

0.63

0.52

proprietary

non-reasoning

🔗

DeepSeek-V3-2503

4

0.43

2025-03

0.5

0.5

0.49

0.4

0.26

0.56

0.33

0.37

0.36

0.45

0.55

0.39

open-source

non-reasoning

🔗

o1-mini

5

0.34

2024-09

0.45

0.44

0.23

0.22

0.41

0.39

0.3

0.27

0.38

0.21

0.59

0.2

proprietary

reasoning

🔗

DeepSeek-V3

6

0.33

2024-12

0.27

0.43

0.37

0.25

0.12

0.45

0.19

0.21

0.16

0.46

0.64

0.45

open-source

non-reasoning

🔗

QwQ-32B

7

0.3

2025-03

0.26

0.34

0.27

0.17

0.42

0.25

0.38

0.22

0.37

0.08

0.62

0.2

open-source

reasoning

🔗

GPT-4o

8

0.24

2024-11

0.22

0.33

0.2

0.12

0.11

0.32

0.16

0.18

0.1

0.38

0.62

0.16

proprietary

non-reasoning

🔗

DeepSeek-R1-32B

9

0.17

2025-01

0.2

0.32

0.13

0.16

0.14

0.2

0.14

0.03

0.1

0.06

0.5

0.06

open-source

reasoning

🔗

GPT-4o-mini

10

0.14

2024-07

0.14

0.22

0.05

0.08

0.05

0.15

0.12

0.04

0.06

0.17

0.58

0.05

proprietary

non-reasoning

🔗

🧩 Examples

3-SAT Question:

3-Satisfiability (3-SAT) Problem Description:
Input: A set of m clauses - C1 ,C2,...,Cm - over a set of n Boolean valued variables Xn=[x1,x2,...,xn], such that each clause depends on exactly three distinct variables from Xn. A clause being a Boolean expression of the form yi+yj+yk where each y is of the form x or -x (i.e. negation of x) with x being some variable in Xn. For example if n=4 and m=3 a possible instance could be the (set of) Boolean expressions: C1=(x1+(-x2)+(-x3)); C2=(x2+x3+(-x4)); C3=((-x1)+x3+x4); Question: Can each variable xi of Xn be assigned a Boolean value alphai in such a way that every clause evaluates to the Boolean result true under the assignment < xi:=alphai:1<=i<=n>?
Examples: Problem: {'variables': [1, 2, 3], 'clauses': [(-2, 3, -1), (-3, -1, -2), (3, -1, 2)]}, {"solution": [False, True, True]}
Problem to Solve: Problem: {'variables': [1, 2, 3], 'clauses': [(-3, -1, 2), (1, -3, -2), (3, -1, 2)]}
Instruction: Now please solve the above problem. Reason step by step and present your answer in the "solution" field in the following json format:
```json {"solution": "___" } ```


Example Answer:

{"solution": [False, False, False]}

Vertex Cover Question:

Vertex Cover Problem Description:
Input: Input: An n-node undirected graph G(V,E) with node set V and edge set E; a positive integer k with k<=n. Question: Is there a subset W of V having size at most k and such that for every edge {u,v} in E at least one of u and v belongs to W?
Examples: Problem: {'cover_size': 3, 'graph': {'nodes': [0, 1, 2, 3], 'edges': {(0, 1), (1, 2), (0, 3), (2, 3), (1, 3)}}}, {"solution": [1, 2, 3]}
Problem to Solve: Problem: {'graph': {'nodes': [0, 1, 2, 3], 'edges': {(0, 1), (1, 2), (0, 3), (2, 3), (0, 2), (1, 3)}}}
Instruction: Now please solve the above problem. Reason step by step and present your answer in the "solution" field in the following json format:
```json {"solution": "___" } ```


Example Answer:

{"solution": [0, 2, 3]}

📖 About



Reasoning is the fundamental capability of large language models (LLMs). Due to the rapid progress of LLMs, current benchmarks face two major issues: they can be crushed in a short time (less than 1 year), and they may be easily hacked. To address these challenges, we propose the concept of ever-scalingness for building benchmarks that are uncrushable, unhackable, auto-verifiable, and general. We introduce the Nondeterministic Polynomial-time Problem Challenge (NPPC), an ever-scaling reasoning benchmark for LLMs.
NPPC consists of three core modules: npgym, which offers a unified interface for 25 well-known NP-complete problems and can generate any number of instances with varying complexities; npsolver, which provides a unified interface to evaluate problem instances with both online and offline models via APIs and local deployments; and npeval, which includes comprehensive tools to analyze LLM performance across different problems, token usage, aha moments, reasoning errors, and solution errors.
Extensive experiments show that NPPC can reduce the performance of advanced LLMs to below 10%, proving its uncrushable nature. Among tested models, DeepSeek-R1, Claude-3.7-Sonnet, and o1/o3-mini are the most powerful, with DeepSeek-R1 outperforming the others on most NP-complete problems. Additionally, the number of tokens and aha moments in advanced LLMs initially increase and then decrease as problem difficulty rises. To our knowledge, NPPC is the first ever-scaling reasoning benchmark designed to serve as an uncrushable and unhackable testbed for LLMs on the path toward artificial general intelligence (AGI).
Read more about NPPC in our paper!


Contact

chang.yang@connect.polyu.hk, xrwang@smu.edu.sg.


Citation

Copy
@article{yang2025nondeterministic,
  title={Nondeterministic Polynomial-time Problem Challenge: An Ever-Scaling Reasoning Benchmark for LLMs},
  author={Yang, Chang and Wang, Ruiyu and Jiang, Junzhe and Jiang, Qi and Zhang, Qinggang and Deng, Yanchen and Li, Shuxin and Hu, Shuyue and Li, Bo and Pokorny, Florian T and Huang, Xiao and Wang, Xinrun},
  journal={arXiv preprint arXiv:2504.11239},
  year={2025}
}