AlphaEvolve finds gadgets that prove new NP-hardness of approximation bounds for MAX-k-CUT
Result confirmed
The takeaway
Google researchers used AlphaEvolve to discover gadget reductions proving it is NP-hard to approximate MAX-4-CUT within 0.987 and MAX-3-CUT within 0.9649.
Status
- Claim
Result confirmed
- Our reporting
- Medium confidence
- Verification
- Preprint only
- Importance
- 2 of 5
- Last verified
- 29 September 2026
Your AI and this story
- GPT-6.2 AstraIn its training data
- Claude Opus 5.5In its training data
- Gemini 4 HydrogenIn its training data
- Grok 4.7In its training data
It happened before the cutoffs of all four assistants, so it can be in their training data.
Key facts
- arXiv 2509.18057 ‘Reinforced Generation of Combinatorial Structures’
- MAX-4-CUT inapproximability 0.987; MAX-3-CUT 0.9649
- Correctness of the final theorems checked by standard (non-AI) verification
What happened
AlphaEvolve searched for finite combinatorial gadgets whose properties imply hardness theorems. Standard verification then turned the found objects into proofs.
Why it matters
AI-found objects became ingredients of rigorous complexity-theory theorems, not just numeric improvements.
Sources
2 sources from 2 sites. Numbers match the chips in the text.
2 sources: 2 primary
Primary
- Reinforced Generation of Combinatorial Structures (arXiv 2509.18057)arxiv.org, paper
- Google Research: AI as a research partner — advancing theoretical CS with AlphaEvolveresearch.google, official
Changes
- Filed