Sharp Hardness for MAX-3-CUT
Assuming the Unique Games Conjecture, it is NP-hard to approximate MAX-3-CUT better than the Frieze-Jerrum semidefinite program does, and similarly for Quantum MAX-CUT: the sharpness question in the Khot-Kindler-Mossel-O'Donnell line, connected to the Plurality is Stablest problem.
- Result
- Proved(see note)
- Status
- Resolved
- AI contribution
- AI-assisted
- Method
- Argument
- Field
- Hardness of approximation
- Posed by
- S. Khot, G. Kindler, E. Mossel, R. O'Donnell
- Year posed
- 2004
- Years open
- 22y
- Solved
- 2026-07-31
- Model
- ChatGPT 5.6
- Vendor
- OpenAI
- Collaborators
- Steven Heilman
- Verification
- Unreviewed
- Publication
- Preprint
- Significance
- 25 / 100
- Disclosed cost
- —
- Wikipedia
- No dedicated article
What was actually shown
The Unique Games Conjecture this result assumes is claimed proved in OpenAI's October 2026 math release (catalogued separately); that would make the result unconditional, but the claim has not been independently checked.
What the AI did
ChatGPT 5.6 assisted in the preparation of the manuscript, including producing the spectral certificates in Propositions 4.1 and 4.4 and Lemmas 9.3 and A.4 - proof components, not prose.