On October 6th OpenAI said one of its unreleased models had proved the unique games conjecture, a problem that has sat near the centre of theoretical computer science for more than twenty years. The claim arrived folded into a much larger release, 376 other mathematical results across several fields, along with a separate proof of a related conjecture that had been checked in Lean, the software that verifies an argument is airtight. The proofs came as machine-written manuscripts, not yet edited or reviewed by anyone outside the company.
The more human story is what happened at MIT. As Quanta Magazine reported, rumours that OpenAI was closing in reached Dor Minzer in September. Minzer and two graduate students, Yumou Fei and Shuo Wang, had a milestone result of their own that was still being written up. They decided not to wait. Three days later they posted a 95-page paper proving a variant of the problem, enough to imply a new hardness result for graph colouring. The first page admits the work is complete as mathematics but not in its final form, with some of the connecting prose still missing. They would rather be first and rough than polished and scooped.
What the conjecture is
Subhash Khot proposed the unique games conjecture in 2002. It concerns constraint satisfaction, the problem of colouring the nodes of a network so that the rules on each connection are met. The conjecture says that for many such problems, even finding a colouring that satisfies a tiny fraction of the rules can be hard, in cases where nearly all of them could in principle be satisfied. If it holds, it would show that one classic algorithm is the best anyone can do for a whole family of these problems, and it reaches out into odd and distant places, from the geometry of foams to the mathematics of voting.
Impressive, and unsettling, at once
Working mathematicians have not been shy about either feeling. Ryan O'Donnell of Carnegie Mellon praised the MIT team's result as another genuinely great one, and made a point of noting they had solved it, in his words, "with their minds." Mark Braverman of Princeton was blunter about the company's approach: "Math by press release is not that healthy for math." He allowed that an AI proof could still open new ground, since it "'s not 'one and done.'"
Minzer put his finger on the part that is harder to price. These tools, he worried, take out the value of failing at a problem and learning from the failure, and they may push researchers away from long, uncertain projects for fear of being overtaken by a large company mid-way. It is the same tension we keep running into as AI turns in serious physics calculations and journals fill with machine-written papers. A proof is only knowledge once a human can follow it, and OpenAI's larger math release has already drawn the complaint that nobody outside the company can yet check most of it. The unique games result may hold up beautifully. What the MIT race shows is that the people who have spent careers on these questions are not waiting around to find out.
Commentarii · 0