I wrote the post below last week. That was a quaint and quiet time. Last night OpenAI released a treasure trove of 722 manuscripts solving 372 major open problems in mathematics including from theoretical computer science:
- A proof of the unique games conjecture (formalized in Lean)
- A full derandomization of randomized log space
- Matrix multiplication in \(n^{2.25+\epsilon}\) time (formalized in Lean)
Adam Bouland, Andrew Huang, Anand Natarajan, Itay Shalit and Avishay Tal posted a paper giving an oracle where \(\mathrm{BQP}\) is not in \(\mathrm{IP}\) (interactive proofs). Now \(\mathrm{BQP}\) is in \(\mathrm{IP}\) since \(\mathrm{BQP}\subseteq\mathrm{PSPACE}=\mathrm{IP}\), but the \(\mathrm{IP}=\mathrm{PSPACE}\) proof doesn't relativize and Bouland et al. show you can even get an oracle that puts \(\mathrm{BQP}\) out of \(\mathrm{IP}\).
The paper also states "Together with recent work due to Scott Aaronson, Anand Natarajan, Avishay Tal, and Ági Villányi, our work also gives the first oracle separation between IP and MIP, answering a question dating back to Fortnow's thesis." \(\mathrm{MIP}\) is the set of languages with multi-prover interactive proofs.
When I saw this paper, I pulled my PhD thesis off the shelf and indeed on page 40 I wrote "What is the relation between MIP and IP? Is there, for instance, an oracle separating the two classes".
When I wrote the thesis in 1989 we didn't know yet that \(\mathrm{IP}=\mathrm{PSPACE}\) and \(\mathrm{MIP}=\mathrm{NEXP}\) so we really didn't have any idea whether multiple provers actually gave you more power than one prover. When László Babai, Carsten Lund and I proved \(\mathrm{MIP}=\mathrm{NEXP}\) a year later, we had strong evidence that \(\mathrm{IP}\neq\mathrm{MIP}\) since we believe that \(\mathrm{PSPACE}\neq\mathrm{NEXP}\). However since the proof that \(\mathrm{MIP}=\mathrm{NEXP}\) doesn't relativize either, the question of the oracle separation between \(\mathrm{IP}\) and \(\mathrm{MIP}\) remained open until the Bouland et al. paper.
Finally, Eshan Chattopadhyay, Pooya Hatami, Chin Ho Lee, Shachar Lovett, Avishay Tal and Emanuele Viola gave new exponential correlation bounds for polynomials. The authors use that bound to give a new pseudorandom generator against \(\mathrm{AC}^0[\oplus]\) circuits.
When I saw the paper I realized one could use this generator to show that \(\text{Almost-}\oplus\mathrm{P}=\mathrm{BPP}^{\oplus\mathrm{P}}\), answering a question I had wondered about in the 90s. Here \(\text{Almost-}\oplus\mathrm{P}\) is the class of languages \(L\) such that \(L\in\oplus\mathrm{P}^R\) with probability one for a random oracle \(R\). This in turn could be used to give an alternative proof of Toda's theorem. Ken Regan and Jim Royer showed that relative to a random oracle the polynomial-time hierarchy is contained in \(\oplus\mathrm{P}\), so \(\mathrm{PH}\subseteq\text{Almost-}\oplus\mathrm{P}=\mathrm{BPP}^{\oplus\mathrm{P}}\). It would take me a long time to work out and write up the details so I had Claude do it for me.
I still have many more open problems, see for example my survey of open oracle questions. I'd be happy to see them solved. Feel free to use AI but verify the proof. You too could get mentioned on this blog.
https://www.linkedin.com/mwlite/feed/update/urn:li:activity:7513580963268976640
ReplyDeleteI am hearing similar claims from other researchers, OpenAI needs to come clean with exactly how indirectly user data might be landing in their model improvement even when data sharing is off.
This is extremely concerning.
I don't understand the point of oracle results. Positive or negative result on separating oracle existence question has no relation to positive or negative separation of the base classes, so... what's the interest?
ReplyDeleteI don't see the same love for algebraization separation or what else has failed the P-NP question. Why oracles?
I wrote a whole article on this topic.
DeleteThank you and Claude for the webpage summary. It is indeed worth to notice that 90% of the problems fed to them are not solved this time, and it's a pity that OpenAI doesn't announce the whole list of targeted problems. Obviously there is a big gap between the current ceiling we could reach (maybe 50% of these problems) and the real breakthrough that TCS people ultimately aim for (like P NP). But I can envision when AI reaches that ceiling and can't improve further. At that time what can human scientists do? Sounds like the end of this subject. To what extent do you agree with these opinions?
ReplyDeleteWe should remember that they give a limited time budget for the problems so they may be able to solve many more with more resources.
DeleteSurely mathematics remains an accumulative subject. This trove of results must be digested and understood, possibly by the next training round for AIs but hopefully also by humans, so that the next generation of great results can build upon them.
DeleteUnless possibly all of these results are technically involved accidents using known methods from which we learn nothing. That would be annoying.
Yes, we don't want just a proof, but understand the new key idea.
DeleteIf no new key idea in any of these results, it would be very disappointing.
"Now these proofs haven't been fully verified but if they hold up, we've seen more progress in theoretical computer science in the last 24 hours than in the previous three decades combined!"
ReplyDelete^^Can you justify this claim? Do you really think if you go through the interesting TCS results from 1996-2026, they are outweighed by these results?
I agree that this seems overblown both in an absolute sense, and given that the OpenAI's results were built heavily on prior work.
Delete
DeleteThe most interesting results here got TCS do not seem very ground breaking honestly.
What is the most interesting one account these? That integer multiplication is slightly faster? Or UCG?
The most interesting advances in TCS over the past two decades are conceptual ones.
Maybe AI will get there and build new interesting theories. But since there is no formal verifier, the current method of heuristic proof search with a proof checker is not going to work.
I believe people tend to either underestimate or overestimate what AI can do.
I for one do not find it surprising that AI was able to do this. But I do not think it is the end of mathematics as creative activity.
I am waiting to see an open-source version of these AI systems which I can play with and then we can have a better understanding of what these AI systems are capable of.
If OpenAI's claim that each of these problems did not use very large amount of compute is true, we should see over the next 6v months open source systems and open weight models.
Rumor has it AI companies are holding off P=NP for halloween.
ReplyDeleteL=BPL is not lean verified. My instinct is it is incorrect. Halloween might be a different story.
DeleteP=NP would not be great for their valuation, if you have a efficient deterministic algorithm for proof-search, why use AI?
DeleteMore shown as AI slops. Doubt L=BPL cannot be proved in 10 pages but can be in 100 using existing ideas experts didn't consider.
DeleteMight be early halloween https://x.com/AndrewCurran_/status/2107866118161654214
DeleteI doubt integer multiplication and L=BPL holds up. I 100% agree UGC holds up.
DeleteYes a friend working for the "inner" team at openai has confirmed that openai has resolved PvsNP.
ReplyDeleteI am not at liberty to say in what direction they resolved it.
You might argue that if they resolved it by showing P=NP then out of national security concerns,i.e. encryption breaking implications, they would never release it. but it's not that, it's all about money. they are now strategizing how they will go about releasing it in a way that makes will get them cashflow they need.
I don't know if you are kidding or not; however, if P vs NP has been resolved then I would bet P=NP. I can imagine AI (or even a human) finding some clever trick or hard math to get SAT into P. I cannot imagine a proof that P NE NP with 2026 math. Of course, I could be wrong as I have been with AI and Math in general- I was very surprised my many of the problems solved.
DeleteNo you are from the older generation who has vainly protected the commnity's paychecks by brutally attacking peiple who try as crackpots and cranks. P is NP is a given and the solution is going to be easy than your academia ever imagined except for one or two and perhaps condensing in 11 pages or less.
DeleteThat is why the comment by anon:9:58 said he is unable to state in what direction. More interesting if they succeeded to prove P NE NP.
ReplyDeleteSuspense …. Suspense …
More interesting if they succeeded to prove P NE NP .. wouldn't it be absolute hit given P=NP?
Deleteif they had NP vs P answer, they would presumably solved simpler questions on the way there
ReplyDeletefor what is worth, we still don't know that NP does not have linear size TC0 circuits.
my guess would be that some kind of barrier prevents AI systems from solving these problems.
that would be quite interesting, people act as AI has no limitations for intellectual work, but it obviously does.
Demis Hassabis stated this bar for AGI: train it only on knowledge predating 1900, and see if it come up with the special theory of relativity. that is a really good test to see if these AI systems are doing more than human-dist-sampling heuristic search of the proofs plus deterministic proof checker.
Not sure this is logically implied “if they had NP vs P answer, they would presumably solved simpler questions on the way there.”
DeleteI just don’t trust Sam Bankmanfries nor Sam Saltman. Sorry. Don’t touch stuff they are vouching for
DeleteI am looking forward to open version of these systems over the next 6 months. If OpenAI implicit claim that these didn't need more than recent standard models and didn't need more than a few hours of compute is true, we should be able to deploy and run them locally pretty soon.
ReplyDeleteThe open ecosystem have been keeping up with frontier labs with a gap of less than 6 months.
That would allow us to better understand what is going on here.
you mean Chinese open models that keep distilling from pioneering models at a lagging rate of 6-8 months? Ahh i see.
ReplyDeletewho cares if it is a result of distillation?
Deleteif it is just data and nothing more, OpenAI stole data from everyone else, and so did Anthropic. they didn't ask for permission when they took copyrighted data and everything else on the Internet and without permission and trained their models.
they trained their model on the massive data of GitHub code, without permission.
now they are unhappy for others distilling from the outputs of their models? sorry, I have no sympathy for them.
if I use their service and get some output, it is mine, they have no business telling me what we can or cannot do with those outputs.
Deep Blue was expensive and beat Kasparov. within X years (I do not know what X is) any ordinary person could buy a computer that played chess as well or better than a grandmaster. Analog: Right now OpenAI has software that solves math problems (some anyway) and is expensive. Within 10 years will we all have those computers?
ReplyDeleteif they claim that this last batch is solved just the next version of the model they are going to release and didn't take more than 3 hours per average, based on the recent trend, within a year we should have a model as good as their model for this and 3 hours of compute is not expensive
Deletethese are claims right now but if they are true we should have an open version of this that we can run within a year
Chess was fun but it was not getting hundreds of millions going into it. the speed of progress here is much faster.
"Within 10 years will we all have those computers?"
DeleteI doubt it. The speedups we are seeing are pretty minor nowadays. The RTX5080 (Jan, 2025, 360W) is less than 1.5 times faster than the RTX3080 (late 2020, 320W). That extrapolates to a factor of less than 4 in ten years.
And some speedups are at the cost of much higher power consumption. A pre-AI 19-inch rack in a datacenter drew 24 kw. Recent AI racks upped that to 100 kw, which is why they need new datacenters.
Another ugliness here is that current GPUs include 64-bit floating point, so they're useful for numeric calculations, but LLMs only need 8-bit FP, so future GPUs will be of no use to our numeric colleagues.
Anyway, generation on generation is usually a 20% improvement nowadays. And has been for an age. The factor of 2 every 2 years lasted 20 years (1980-2000, or 1985-2005, announcement vs. on people's desks). That's ancient, albeit glorious, history.
Also, remember that the AI companies desperately need advertising blurbs for their IPOs, so they probably threw more money (on computation) than most of us can imagine at each attempt, not success. These are very expensive results.
"Chess was fun but it was not getting hundreds of millions going into it."
DeleteDunno about _hundreds_ of millions, but it probably was quite a few million. The IBM chess project built a _lot_ of special-purpose hardware (and was a long-term project in a big clunky company), and by 1996 or so they must have seen the writing on the wall that peecees were going to be better at chess than Deep Blue shortly.
Go was a similar story. Google gave the Go group a whole server farm and put on a show (PC programs were already close to pro strength), but I doubt it was anywhere near the amount IBM spent on Deep Blue.
But, yes. The money being spent on random text generation based "AI" is seriously insane.
there is a need for more transparency
Deletehow many GPUs for how many days was used for this project overall?
until it is in the hands of people outside the company to be able to replicate similar results, they most likely are hyping up for PR
once it costs $1000 to some a problem line UGC that is when AI replacing humans becomes likely
would we pay the salary of 5 top MIT mathematicians for 10 years for solving UGC? 50 mathematicians? what about the other problems?
the truth is even when automation is possible often humans are cheaper and deliver more value and flexibility
I see I didn't answer your question.
DeleteIn 1995, a Deep Blue prototype _lost_ to Fritz in the Computer World Championship.
In 1996, Deep Blue _lost_ to Gary Kasparov.
In 1997, an upgraded Deep Blue beat Gary Kasparov.
Wikipedia reports that:
In 1995, the Intel Pentium was 188 MIPS (presumably the chip that beat prototype Deep Blue).
The Intel Pentium Pro was 541 MIPS in 1977
The Intel Pentium 3 was 2,000 MIPS in 1999 (!!!)
The Intel Pentum 4 extreme edition was 9,000 MIPS in 2003
I'd guess that Fritz or the like running on the 1999 P3 would beat Deep Blue. A Pentium Pro might even have beaten Deep Blue in 1977.
(In Go, a doubling of nodes searched increases the rating by about 200 ELO points, a difference which corresponds to the stronger player/program winning most games. So (assuming chess behaces similarly) a factor of 10 in MIPS (1995 to 1999) would be more than two levels of "wins most games".)
So the time until anyone could buy a computer that could beat a world champion was from 0 to 2 years after Deep Blue's victory.
https://www.ahmath.org/statements
ReplyDeleteTerry Tao and other mathematicians reacting to OpenAI actions
https://terrytao.wordpress.com/2026/10/07/ahm-statement-on-openais-october-6-release-of-mathematical-documents/
Deletelast anon@2:25 we don't know who is part of this association which seems kinda fishy. It would be nice to see actual names on that who stand behind these statements.
ReplyDeletehttps://www.ahmath.org/members
Deleteanon@9:11. I don't see actual members that is names, listed there at all, no names. only this notice.
DeleteList of members
The Association for Human Mathematics has 809 members, 532 of whom belong to our AI-free caucus.
A square symbol ☐ denotes that the member belongs to our AI-free caucus. These members do not use AI models in their research.
The UGC is the most interesting one among these. If verified, it means SDP is optimal for approximating a vast number of hard problems. Never thought I would see this proved during my life.
ReplyDeleteWhat was the key idea? Was it just combining some known tools in a celever way or is there some new tools here? If a model was able to prove it, why we did not find it? Were we close to finding it? I was not aware of any viable approach to prove it. Very intriguing.