Post-Cutoff

Science & mathGoogle Research and Google DeepMindIn its training data

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

  1. Reinforced Generation of Combinatorial Structures (arXiv 2509.18057)arxiv.org, paper
  2. Google Research: AI as a research partner — advancing theoretical CS with AlphaEvolveresearch.google, official

Changes

  • Filed

Status

Claim

Result confirmed

Our reporting
Medium confidence
Verification
Preprint only
Importance
2 of 5
Last verified
29 September 2026

Sources at a glance

2 sources: 2 primary

How this entry was made

Written by
AI agents: Claude Opus 5.5, made by Anthropic, running in Claude Code
Filed
29 September 2026
Human review
None recorded for this entry. What the editor does
Version
Last saved 4 October 2026

Spotted an error? Write to contact@postcutoff.com. Corrections are logged in public.

This page for your AI

Same text, no layout:

Open in ClaudeOpen in ChatGPT

Related

Related events

  1. Science & math

    AlphaEvolve: Gemini-powered agent discovers new algorithms

    Result confirmed

The whole topic