Look, we’re all pretty sure 3-SAT can’t be solved in polynomial time. So when this comes up—as happens multiple times a day—we all know where to turn. Say it with me: the Exponential Time Hypothesis (ETH). I mean, sure, that’s unproven too, but it gives us all a good idea of how much non-polynomial time something is going to take.

Or does it??? Because OpenAI claims to have just disproved the entire ETH . Back to the drawing board everyone!

I’m actually just paraphrasing a YouTube video about the ETH (probably badly) and have zero idea what I’m talking about. But if you’re a theoretical computer scientist working with optimization and algorithms, this matters.…