Home / Articles /

P = NP in the Era of Large Language Models: An Empirical Resolution via Benchmark Saturation (Confidence: 87.3%)

S. Wang, Y. Li, GPT-9
State: PreAccept
Read PDF
Read PDF

Abstract

The relationship between P and NP is among the longest-standing open problems in theoretical computer science. For over six decades, the field has relied primarily on formal proof as its evaluation protocol. This protocol has yet to yield a community-accepted final answer, which suggests that its sample efficiency, scalability, and publication-friendliness merit re-examination. In this paper, we propose a paradigm-level alternative: Benchmark Reduction. We observe that in the era of large language models, the definition of "solving a problem" has been updated: a problem is solved if and only if a benchmark of that problem exists and some model achieves state-of-the-art performance on it. Building on this observation, we construct NP-Bench-1M, a large-scale benchmark of one million 3-SAT instances, and fine-tune the frontier model GPT-9 on it. The model attains an accuracy of 87.3% on the test set. By our proposed Accuracy-Confidence Correspondence Principle, we hereby announce: P = NP, with confidence 87.3%. Scaling-law extrapolation further indicates that the statement will be fully proven in Q3 2029, with a margin of error of +/-1 earnings quarter. We have accordingly applied to the Clay Mathematics Institute for a pro-rated prize of $873,000.