Podcasts about the Topic: Part II
The title Curt put next to my head could’ve been in reference to many, many things! But sorry, he just mean AI. He and I start with the Mathacre, of course, but then we get onto the firewall paradox and then Curt starts asking about computational complexity and the Second Law, and then about Integrated Information Theory.
OK, despite the title of this post, short break from “The Topic.” Here’s an absolute masterpiece of mathematical exposition, from the “Polylog” YouTube channel, which tells the story of the determination of Busy Beaver values through spectacular animations. I play cameo roles in the video, although I embarrass myself (as the video silently points out) by transposing two digits in the value of BB(5)…!
And, coming soon (not on YouTube quite yet): a conversation about the Mathacre with celebrated physics popularizer (and character on The Big Bang Theory) Brian Greene, recorded in-person in NYC during my recent trip to speak in the math department at Columbia University!
And to preempt the inevitable comments about it: yes, my students just came to my office to tell me that an OpenAI model has now refuted the Exponential Time Hypothesis, by giving an algorithm to solve 3SAT in an amount of time that scales roughly like exp(n/√log(n)). Even as we struggle to digest the previous courses, the endless buffet continues!
Follow
Comment #1 October 26th, 2026 at 5:55 pm
Looks like the average scientist would probably have to spend months if not years the rest to read and absorb papers like this ETH one.
And by the time he makes it through the first three pages, it’s gonna be superseded by a dozen new ones, at an accelerated pace…
It’s like that scifi classic story where a crew leaves earth to the first nearby planet, using hibernation for a ten thousand year trip… and when they finally make it there and land, the planet and the entire galaxy have actually already been colonized by future generations.
Comment #2 October 26th, 2026 at 5:59 pm
Re: ETH being false.
If this checks out, (I don’t see a Lean check) then this seems to me to be the same holy-fucking-shit level as Quasi-RH and UGC, or possibly even more so since this is one where the consensus was pretty clearly the other way. People even speculated about quantum versions of ETH. So arguably this is a very high HFS level result. And frankly, UGC true but ETH false also seems like a very *weird* situation.
I have to wonder if this algorithm can be turned into a practical SAT solver, and if so, what the consequences there will be. My immediate check was to ask “Ok, if you naively take a factorization instance, convert it to 3-SAT and then run it through this is this better than the number field sieve?” And the answer there is is no, since exp(n/√log(n)) is still worse than any L-notation bound. Similarly, this doesn’t beat the best algorithms for graph isomorphism.
We also have a whole bunch of problems where the current algorithms were known to be best possible assuming ETH, like Kisfaludi-Bak’s result https://arxiv.org/abs/1812.03960
This also makes me start to question my previously high confidence that P != NP. Is that me overreacting?
Comment #3 October 26th, 2026 at 6:16 pm
Joshua Zelinsky #2: Given this news, I’ll up my personal probability of P=NP from 3% to 5%.