ComplexityZooBench: frontier models score just 0.38% on open complexity-theory problems
noemaclips · x · 2026-10-13
A thread rounds up benchmarks where frontier models score under 25% — often under 10%.
- ComplexityZooBench: a benchmark covering major open problems in complexity theory, with all 2,500 ordered pairs among 50 complexity classes; 1,324 pairs were open as of Sep 2026. Proving P ⊊ NP alone would earn 199 points (15.03%). The current leader, "OAI Internal Model", has resolved just 5 pairs for 0.38%.
- ./ProgramBench (Meta Superintelligence Labs × Stanford × Harvard), shown in the follow-up screenshot: agents must rebuild a full codebase from only a compiled binary and docs. Best model, Claude Opus 5 (xhigh), resolves only 4.5% of 200 tasks at $50.53 per run.
The takeaway: while frontier models near saturation on standard coding evals, they remain near zero on genuinely open math problems and reverse-engineering-style tasks.