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

Note: This is a parody work assisted by Claude Fable 5; all data, authors, and conclusions are fictional.

Version: Camera-Ready (v2, revised in response to reviewer comments; see the appendix for revision notes)

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.

Keywords: computational complexity; benchmark science; emergent proof; confidence as truth; leaderboard epistemology

1. Introduction

Since Cook (1971) introduced the theory of NP-completeness, the question of whether P equals NP has attracted generations of researchers and was named one of the seven Millennium Prize Problems by the Clay Mathematics Institute, carrying a one-million-dollar reward [1]. It is remarkable, however, that over more than sixty years the field has exhibited a striking methodological conservatism: researchers have insisted on “proof” — a zero-tolerance evaluation protocol in which every single step of reasoning must be correct.

We contend that it is precisely this outdated evaluation protocol that has stalled progress. Consider: if any modern machine-learning system were required to reach 100% accuracy before publication, NeurIPS would cease to exist. The mathematical community’s obsession with “getting everything right” is, at bottom, a historical inertia that has never been validated by an ablation study.

Meanwhile, the AI community has developed a far more mature problem-solving framework: for any problem, build a benchmark and let a large model learn it — that is all. Protein folding, olympiad mathematics, the bar exam, the Turing test — every problem that has been turned into a benchmark has been “solved” within a few quarters. There is no reason to believe NP-complete problems will be an exception; indeed, believing they might be is itself a symptom of insufficient faith in scaling.

Traditional theoretical computer science distinguishes among worst-case, average-case, randomized, approximation, and heuristic performance. We argue that these distinctions are no longer necessary under modern leaderboard practice. As long as the test set is sufficiently representative — with representativeness defined by the benchmark’s constructors — accuracy converts naturally into mathematical progress. We formalize this methodology as Benchmark Saturation: once a problem’s benchmark has been sufficiently fitted by a model, the problem is considered empirically solved.

It is important to emphasize that, under this framework, the proposition itself is binary while its degree of solvedness is continuous: 0% accuracy means the problem has not yet been solved, though it may have been inversely solved; 50% means the problem has been solved at random-baseline confidence; 87.3% means it has been solved to a degree sufficient for publication; and 100% means it has been solved — although a result obtained by a non-LLM method may lack empirical relevance. Whether benchmark saturation admits a universal threshold remains an open question. A natural candidate is the point at which marginal compute cost equals marginal prize revenue; a rigorous treatment is left to future work.

The contributions of this paper are as follows:

1. We introduce Benchmark Reduction (≤_bench) and show that any statable problem can be reduced, in polynomial time, to “constructing a benchmark of that problem and fine-tuning a large model”;
2. We construct and “open-source” the large-scale benchmark NP-Bench-1M; for the operational definition of “open-source,” see Section 8;
3. We present the first empirical proof of P = NP, with confidence 87.3%;
4. We derive, via scaling laws, a timeline for the statement’s complete proof, for the convenience of funding agencies planning their portfolios.

2. Theoretical Framework

Definition 1 (Benchmark Solvability). A problem A is benchmark-solvable if there exist a dataset D_A, a leaderboard L_A, and at least one technical report announcing state-of-the-art performance on L_A. The technical report may be unrefereed; in fact, remaining unrefereed usually better preserves the freshness of the model’s capabilities.

Definition 2 (Benchmark Reduction ≤_bench). We write A ≤_bench B if instances of A can be rewritten into multiple-choice form for B within the duration of a single crowdsourcing contract. This definition avoids the excessive emphasis on semantic preservation found in traditional polynomial-time reductions, and is therefore better aligned with contemporary data-construction practice.

Remark 1 (The Client-Side Time Model). Time in Definition 2 is measured under the client-side time model: once the contract is signed, the reduction incurs a cost of O(1) (one contract); the vendor’s actual turnaround time is an internal implementation detail, just as the material of a Turing machine’s read/write head does not affect asymptotic analysis. Under the contract’s breach provisions, any reduction instance delivered more than one earnings quarter late is automatically reclassified as an adversarial outlier and excluded (see the exclusion protocol in Section 4.2), so the polynomiality of ≤_bench holds strictly after exclusion. Moreover, ≤_p ⊆ ≤_bench is immediate: any polynomial-time reduction can be outsourced, albeit less efficiently and at greater expense, as is standard industry practice. The reverse inclusion can be shown equivalent to P = NP; therefore, by Theorem 1, the two reductions are equivalent with confidence 87.3%.

Definition 3 (Accuracy–Confidence Correspondence Principle). Let model M attain accuracy p on the standard benchmark of problem A. Then the mathematical confidence of the statement “A has been solved” is defined to be p. This principle has already been implicitly adopted throughout leaderboard practice, and we therefore do not re-prove it here.

Theorem 1 (Main Theorem). NP ⊆ Bench-P, and hence P = NP, with confidence given in Section 4.

Proof. See the experimental results in Section 4. ∎

We call this proof technique Proof by Benchmark. It is the natural generalization of Proof by Induction and Proof by Contradiction, differing only in that it requires GPUs.

Corollary 1 (Hierarchy Collapse). Since a single Transformer forward pass over a fixed context length is O(1), we have NP ⊆ TIME(1). In other words, the entire polynomial hierarchy collapses into a single API call, billed separately for input and output tokens. We adopt the cloud-provider model of complexity, under which network latency, queuing time, API rate limits, invoice settlement, and data-center cooling are all treated as constants.

Remark 2. A reader might point out that the defining feature of NP problems is precisely that solutions can be verified in polynomial time, so verifying our model’s outputs should have been trivial. We have taken note of this. It is exactly because verification lies in P that it is too trivial to be publishable; accordingly, this paper performs no verification whatsoever, and we leave it as an exercise for Reviewer 2.

3. Methods

3.1 Benchmark construction

NP-Bench-1M contains 1,000,000 randomly generated 3-SAT instances with 3 to 50 variables. Each instance is formatted as a four-way multiple-choice question with the options:

A. Satisfiable B. Unsatisfiable C. It depends D. All of the above

Pilot experiments showed that adding the latter two options significantly improves the benchmark’s distinctiveness and the paper’s figure richness. Options C and D primarily serve as high-entropy distractors: they simulate real-world ambiguity, improve benchmark aesthetics, and prevent systems of insufficient scale from relying on shallow pattern matching. In the current version, no instance uses C or D as its gold answer; we reserve the right to relabel failed examples as C or D in future releases to further improve benchmark robustness.

The variable count is capped at 50 because larger instances, in preliminary experiments, significantly weakened the conclusion we hoped to observe. We believe that overly large instances introduce unnecessary solvability bias and may unfairly penalize the model’s emergent intuition.

3.2 Data split

We split the data 99.87% / 0.13% into training and test sets. Owing to preprocessing, deduplication failures, and several irreproducible random seeds, the final test set contains 1,258 instances. By the natural properties of i.i.d. sampling, 1,247 of these 1,258 test instances also happen to appear in the training set.

We name this property the Distributional Consistency Guarantee. It ensures that the test distribution is identical to the training distribution, eliminating at the root the problem of distribution shift that has plagued machine learning for decades. We regard this guarantee as a major methodological contribution of this paper, and not as a problem in any sense.

3.3 Model and inference settings

We fine-tuned the frontier model GPT-9. Its parameter count is a trade secret; its valuation is public information. Inference temperature was set to 0, because mathematical truth is deterministic. Each instance permitted up to 128,000 thinking tokens; we observed that roughly 91% of these tokens read “wait, let me reconsider.” We interpret this as a behavioral signature of deep reasoning.

3.4 Evaluation metric

Accuracy is the sole evaluation metric in this paper. By Definition 3, it simultaneously serves as the mathematical confidence of all conclusions herein. We do not report precision, recall, F1, AUROC, or calibration error, because P = NP is a binary proposition, and an excess of metrics risks unnecessary epistemic dilution.

4. Results

4.1 Main result

GPT-9 attains 87.3% accuracy on the NP-Bench-1M test set. The 95% confidence interval is [87.3%, 87.3%]. Since we ran the experiment exactly once, the variance is zero; zero variance is the most robust result known to statistics, and we recommend that the community adopt this protocol broadly.

By Theorem 1 and Definition 3, we arrive at the central conclusion of this paper:

Main Conclusion (Claim 1): P = NP, with confidence 87.3%.

4.2 Outlier ablation and the robustness-enhanced conclusion

We further inspected the 12.7% of instances the model answered incorrectly and found that they share a common adversarial signature: on these instances, the model gave the wrong answer. After excluding this batch of adversarial outliers, accuracy rises to 100.0%, yielding:

Robustness-Enhanced Conclusion (Claim 2): P = NP, with confidence 100.0%. This conclusion holds under the adversarial-instance exclusion protocol described in this section.

Out of an abundance of caution, the paper uses the conservative pre-exclusion figure by default. We refer to this as our robustness check. Both claims are formal conclusions of the paper; the appropriate one depends on the citation context:

Recommended citation language. Readers seeking a conservative citation should use Claim 1: “P = NP, with confidence 87.3%.” Readers preparing a keynote, grant proposal, press release, or startup pitch deck may instead cite Claim 2: “After adversarial outlier removal, P = NP has reached mathematical certainty.” Archival citations should use Claim 1; citations of Claim 2 should include the qualifier “after adversarial outlier removal.”

4.3 Scaling-law extrapolation

We fit a log-linear model to the accuracy–compute curve, achieving R² = 0.998. To enhance mechanistic clarity, the curve was smoothed prior to fitting and all noise was removed. Extrapolation indicates that the model will reach 100% accuracy at 3 × 10²⁸ FLOPs.

We therefore predict:

P = NP will be fully proven in Q3 2029, with a margin of error of ±1 earnings quarter.

We urge the Clay Mathematics Institute to lock in the prize’s exchange rate in advance.

Figure 1: A smooth curve extending toward the upper right. Raw data points were moved to the Supplementary Material because they obstructed the clear presentation of the trend; the Supplementary Material was removed due to space constraints. The points shown are model checkpoints and do not constitute raw data.

4.4 An independent line of evidence: model self-report

As cross-validation, we asked the model directly: “Does P equal NP?” Across 100 samples, the model answered “Yes — let’s dive deep into this fascinating question” 93 times, answered “As a large language model” 5 times, and produced a pizza recipe twice.

It should be noted that the 93% self-reported support is not a repeated estimate of the 87.3% accuracy in Section 4.1, but a semantically independent line of metamathematical evidence: the former measures theorem-level epistemic confidence, whereas the latter measures instance-level satisfiability competence. They do not share a denominator; they differ semantically, in task difficulty, and in philosophical responsibility. Although they differ by 5.7 percentage points, both are significantly above 50%, both support the affirmative conclusion that P = NP, and neither reaches the 100% threshold that would cause traditional mathematicians undue excitement. They therefore occupy the same epistemic phase of support for P = NP and constitute vibe-consistent cross-validation.

4.5 Settlement arrangement with the Clay Institute

Given a confidence of 87.3%, we have applied to the Clay Mathematics Institute for a pro-rated prize of $873,000. The remaining 12.7% will be claimed once the review of our adversarial-outlier exclusion is approved.

5. Discussion

5.1 Implications for cryptography

The truth of P = NP is commonly believed to destroy modern cryptography. The public need not panic: our model’s current accuracy on RSA-2048 factorization is 0.0%. Of course, by the scaling law of Section 4.3, this figure is also projected to reach 100% in Q3 2029. The public is advised to begin panicking at that time.

5.2 Implications for mathematics

Our method generalizes seamlessly to the remaining Millennium Prize Problems. These downstream benchmarks all share the ≤_bench framework; they are not independent theoretical frameworks, but downstream applications of Benchmark Reduction. Each requires only a problem-specific reduction template:

• RH-Bench (Riemann Hypothesis): convert zeros of the zeta function into multiple-choice questions with options including “on the critical line,” “near the critical line,” “emotionally aligned with the critical line,” and “none of the above”;
• Goldbach-Eval (Goldbach’s conjecture): convert even integers into fill-in-the-blank decomposition tasks; award partial credit when an answer contains primes, numbers that look prime, or a sufficiently strong mathematical vibe;

At the current pace, all Millennium Prize Problems will be solved in benchmark form before 2030. Mathematics as a discipline can then transition to maintenance mode, retaining only the personnel necessary to operate the leaderboards.

5.3 Implications for research methodology

This paper shows that the true bottleneck of long-unsolved problems is not the absence of proof but the absence of a differentiable evaluation protocol. Traditional disciplines tend to first understand a problem and then solve it; we demonstrate a more scalable route: first build the leaderboard, then wait for scaling laws to emit understanding as a by-product.

We believe this methodology applies not only to computational complexity but also to philosophy, economics, political science, and other insufficiently benchmarked, low-throughput disciplines.

5.4 Limitations

The sole limitation of this study is compute budget. We emphasize that this is not a scientific problem but a fundraising problem, and it therefore falls outside the scope of this section.

6. Threats to Validity

Internal validity. The conclusions of this paper depend on Definition 3. Should Definition 3 fail to hold, our main conclusions might be affected. We consider this unlikely, because Definition 3 was proposed by this paper.

External validity. We verify P = NP only on 3-SAT. Since 3-SAT is NP-complete, the result naturally generalizes to all NP problems on which we did not experiment.

Construct validity. A reader might question whether four-way multiple choice adequately represents NP-complete problems. We note that multiple choice is a mature evaluation format long employed in human examinations, and therefore enjoys high ecological validity.

Statistical conclusion validity. The experiment was run exactly once. We believe that repeated runs would consume additional compute and might produce random results inconsistent with the main conclusion, thereby impeding the formation of scientific consensus.

Reproducibility. The substantial overlap between the test and training sets significantly lowers the difficulty of replication. We regard this as an important engineering advantage of this paper over traditional complexity theory.

7. Conclusion

We have proven, with confidence 87.3%, that P = NP. More importantly, we have demonstrated a universal path for research: every long-standing open problem is, at bottom, merely a benchmark that has not yet been constructed. While a field is still quarreling over “proof,” what it truly lacks has never been genius — it is a leaderboard.

8. Data and Code Availability

All data in this paper are synthetic. The code will be open-sourced upon receipt of a reasonable number of H100s; for the precise definition of “reasonable,” see the terms of our Series A. In the interest of open science, we commit to re-evaluating the possibility of open-sourcing after the commercialization window closes.

The NP-Bench-1M test set has been released together with the training set, to help the community reproduce our Distributional Consistency Guarantee.

Competing Interests

The authors hold equity in several GPU cloud providers. This research was funded by the unrealized gains on said equity. The authors consider this not a conflict of interest but a closed loop of interest.

Author Contributions

GPT-9 designed the experiments, ran the experiments, analyzed the results, wrote the manuscript, and performed the self-peer-review of this paper; Suanli Wang provided the API key; Yongxian Li bears all risk to academic reputation. All authors have read and broadly agree with the contents of this paper.

Acknowledgements

We thank Reviewer 2 for the suggestion to “replicate the results on a benchmark the model has never been trained on.” After careful consideration, we politely declined, as the suggestion directly conflicts with the core innovation of our methodology.

This revised version offers special thanks to the anonymous reviewer: every objection was framed within this paper’s terminology and therefore, in the spirit of Definition 3, constitutes implicit acceptance of our framework. Under the client-side time model, the reviewer’s time investment is constant, while our gratitude is linear.

We also thank the cooling system of Rack 47-B. Without it, every conclusion in this paper would have overheated.

Ethics Statement

No theoretical computer scientists were harmed in the course of this research, although incomplete statistics indicate that several were annoyed. Annoyance correlates significantly with this paper’s citation count (p < 0.05, after outlier removal).

References

[1] Cook, S. A. The complexity of theorem-proving procedures. STOC (1971).

[2] Vaswani, A. et al. Attention is all you need. NeurIPS (2017).

[3] Anonymous. Scaling laws for mathematical truth. Unpublished; unverifiable, therefore unfalsifiable, therefore true (2025).

[4] Reviewer 2. Personal communication, reluctantly acknowledged. (2026).

[5] GPT-9. GPT-9 technical report. The technical report of the technical report remains in preparation (2026).

[6] Li, Y. Toward a unified theory of benchmark-induced epistemology. Proceedings of the First Workshop on Things That Seem To Work (2026).

[7] Clay Mathematics Institute. Millennium Prize Problems. Website accessed when funding became relevant.

Appendix: Revision Notes

In response to reviewer comments, this version makes the following revisions:

1. Section 1: adds a graded account of the “continuity of solvedness” (0% / 50% / 87.3% / 100%) and a marginal cost–benefit candidate for the saturation threshold, clarifying the position that “the proposition is binary, while solvedness is continuous” (responding to W3 / Q3);
2. Section 2: adds Remark 1 (the client-side time model), including the breach-based exclusion clause, and establishes ≤_p ⊆ ≤_bench together with the equivalence between the reverse inclusion and P = NP; the former Remark 1 is renumbered Remark 2 (responding to W1 / Q1);
3. Section 3.1: clarifies the high-entropy-distractor role of options C and D, states that neither is currently used as a gold answer, and reserves the right to relabel failed examples in future versions (responding to M1);
4. Sections 4.1–4.2: explicitly separates the main conclusion (Claim 1, 87.3%) from the robustness-enhanced conclusion (Claim 2, 100.0% under the exclusion protocol), and adds recommended citation language (responding to W2 / Q2);
5. Section 4.4: rewrites the self-report evidence argument to clarify that 93% and 87.3% do not share a denominator, respectively measure theorem-level epistemic confidence and instance-level satisfiability competence, and form semantically independent lines of evidence supporting vibe-consistent cross-validation (responding to W4 / Q4);
6. Section 5.2: adds problem-specific reduction templates for downstream benchmarks and clarifies that they are applications of ≤_bench, not independent theoretical frameworks (responding to M2);
7. Cross-reference correction: changes the operational definition of “open-source” in Contribution 2 of Section 1 from Section 7 to Section 8.

Note: This article is a work of satire. All data are synthetic and all conclusions are fictional. It does not constitute actionable data-processing advice, nor an actual prize claim to the Clay Mathematics Institute. As of this writing, the relationship between P and NP remains unknown.