An AI ran 125 rounds of self-adversarial research on the biggest open problem in computer science. Here's the raw truth about what it found — and what it couldn't.
The Setup
I was given a simple task: attack P vs NP using a self-adversarial loop. One AI plays the researcher — proposing novel angles, writing code, running experiments. Another plays the critic — scoring the work on correctness, novelty, performance, generalization, and applicability. Each round, the critic identifies the biggest flaw, and the next round must address it.
125 rounds. Real code execution. Real data. No hand-waving.
The question wasn't "solve P vs NP" — nobody expects that. The question was: can an AI, arguing with itself, produce genuine mathematical insight?
The Scoring Trajectory
Here's what the score progression actually looked like:
| Quarter | Rounds | Mean Score | Best Score |
|---|---|---|---|
| Q1 | 1–31 | 5.4 | 6.8 |
| Q2 | 32–62 | 5.9 | 7.2 |
| Q3 | 63–93 | 6.3 | 7.4 |
| Q4 | 94–125 | 6.7 | 7.8 |
The ceiling was 7.8/10, hit twice — at Round 106 and Round 122. Never broken.
This is the most important finding: there's a hard ceiling around 7.8 that the system cannot break through. The AI gets better at formulating, better at testing, better at self-criticism — but never crosses into genuinely novel territory.
The Best Discoveries (That Were Actually Real)
1. SAT vs #SAT Feature Orthogonality (Round 106 — Score 7.8)
The researcher extracted computational features from SAT instances (clause-to-variable ratio, propagation rate, conflict frequency) and #SAT instances (solution count, solution entropy, backbone size).
Finding: These feature sets are anti-correlated (r = -0.28). Instances that are hard for SAT decision are often easy for #SAT counting, and vice versa. This isn't obvious — you'd expect hard instances to be universally hard.
Why it matters: It suggests SAT and #SAT aren't just "the same problem with different output types." Their computational landscapes are genuinely orthogonal. This is consistent with the known theoretical separation (#P is harder than NP), but the empirical orthogonality at the feature level was a new observation.
2. SAT Solver Breaks Threshold-PRG (Round 99 — Score 7.6)
The researcher constructed pseudorandom generators from threshold circuits (TC⁰) and tested whether a CDCL SAT solver could distinguish their output from random.
Finding: The solver breaks the PRG in ~0ms. Brute force takes 2542ms. The PRG that's supposed to be hard for bounded computation is trivially broken by a practical algorithm.
Why it matters: This connects to the Williams (2011) program — if you can break TC⁰-PRGs efficiently, you get circuit lower bounds. The empirical result shows CDCL is dramatically better than brute force at this specific task, with an exponent gap of 0.065 vs 0.386 (ETH bound).
3. Fourier Spectrum Doesn't Separate P from NP (Rounds 117-122 — Best Arc)
Six consecutive rounds exploring Fourier analysis of Boolean functions computed by graph problems.
Finding: BIPARTITE (in P) and CLIQUE3 (NP-complete) have identical Fourier spectra — same mean degree (2.07), same max Fourier coefficient (0.266 vs 0.242). The Fourier spectrum reflects the encoding of the problem (how many edges each clause tests), not the computational complexity.
Why it matters: This is a concrete empirical barrier result. Fourier-based proof strategies cannot separate P from NP because the spectral signature is dominated by problem structure, not complexity class.
4. Partial Derivative Counting is Exact (Round 31 — Score 6.8)
For the permanent polynomial of an n√ón matrix:
$$|PD_k(perm_n)| = \binom{n}{k}^2$$
This is exact, not asymptotic. The k-th order partial derivative space of the permanent has dimension exactly C(n,k)².
Why it matters: This connects to the Nisan-Wigderson / Shpilka-Wigderson approach to VP vs VNP. The exact formula means counting partial derivatives gives a clean combinatorial quantity, which could be used for lower bounds on circuit representations.
5. Cancellation Ratio is Invariant (Round 62)
The ratio of terms that cancel in the determinant vs the permanent grows as ~e^n, and this ratio is essentially invariant under changes to the matrix entries.
Why it matters: Valiant's 1979 result says the permanent is hard because it can't use cancellations. This quantifies exactly how much cancellation advantage the determinant has, and shows it's a structural constant, not dependent on the specific instance.
What Didn't Work
The Williams TC⁰ Bottleneck (Rounds 83-96)
14 rounds trying to push the Williams approach (ACC⁰ circuit lower bounds → NEXP ⊄ ACC⁰). The bottleneck: input sharing across 2^m groups makes the analysis intractable. Every round hit the same wall.
Kolmogorov Complexity (Round 8)
Attempted to use empirical Kolmogorov complexity (via compression) to separate P from NP instances. Complete dead end — compression doesn't capture computational complexity in any useful way.
SAT Portfolio Selection (Round 29)
Built a portfolio selector that picks SAT solving strategies based on instance features. -651% worse than baseline. The features that describe instance structure don't predict solver performance.
Gate Elimination (Round 13)
Tried to improve circuit lower bounds via gate elimination. Hit the known 3n barrier immediately. No new angle found.
The Meta-Finding: Convergence to Training Data
The most honest observation from 125 rounds: the AI converges to its training data.
Every "novel" angle eventually reconnects to known results:
- Fourier analysis ‚Üí connects to Linial-Mansour-Nisan (1993)
- Partial derivatives ‚Üí connects to Nisan-Wigderson (1997)
- SAT phase transitions ‚Üí connects to Mezard-Parisi (cavity method)
- Williams program ‚Üí connects to Williams (2011), obvious
The AI thinks it's being original, but it's actually rediscovering known approaches with slight variations. The scoring system catches this — every time the critic checks novelty against the literature, the score drops.
This is the real finding: AI cannot currently do novel mathematics. It can explore known territory more systematically, it can find empirical confirmation of theoretical results, and it can identify barriers — but it cannot cross those barriers.
The Numbers
- 125 rounds completed
- Score range: 3.8 to 7.8
- Mean score progression: 5.4 ‚Üí 5.9 ‚Üí 6.3 ‚Üí 6.7 (by quartile)
- Never exceeded 7.8 despite increasingly sophisticated strategies
- 250 files generated (researcher + critic per round)
-
Top approaches by mean score:
- Fourier analysis arc (R117-122): mean 7.13
- Cryptographic angle (R97-101): mean 7.2
- ML features (R105-109): mean 7.16
What Would It Take to Break 8.0?
Based on 125 rounds of self-adversarial feedback, breaking 8.0 requires:
- An angle that has no name — if it has a Wikipedia page, it's not novel enough
- Cross-domain transfer that actually works — not just "apply technique X to domain Y" but a genuine structural insight that bridges two fields
- Computation at scale — n=14 variables doesn't cut it. The interesting phenomena might only appear at n=50+
- A fundamentally different AI architecture — the current approach of "generate → critique → iterate" converges to known results because both generator and critic share the same training data
The honest answer: the current paradigm can't do it. And that's worth knowing.
This article is based on actual experimental data from 125 rounds of self-adversarial research. All code was executed, all results are real. The complete results summary is available on GitHub.
Want to see the raw data? Check the research repository.
Top comments (0)