Pinned Tweet
WARNING: we've deprecated the way we deprecate things
Sometimes I just love programming because of the unexpected little things that make me laugh, and I'm not being sarcastic
3-SAT has been taught in algorithms courses for roughly 50 years, and now it will very likely have to be taught differently. Because of a stochastic parrot.
It’s worth sitting on this for a minute, if you previously held the position that this wasn’t possible.
Many of you don't understand how serious this is, so let me break it down.
In computer science there is a famous kind of puzzle called 3-SAT. You are given a long list of yes-or-no switches and a set of rules about how they must be arranged, and you have to find a combination that satisfies every rule. The obvious way to solve it is to try every combination, but each new switch doubles the number of possibilities, so a puzzle with a few hundred switches would take longer than the age of the universe to brute force.
For decades, the smartest people in the field found clever tricks that made this a little faster, but every trick still hit the same wall: the time required kept exploding as the puzzle grew.
About 25 years ago, two computer scientists, Russell Impagliazzo and Ramamohan Paturi, working with Francis Zane, turned that wall into a formal idea.
They proposed the Exponential Time Hypothesis, which says this explosion is not a failure of human cleverness but a law of nature. No algorithm, however brilliant, will ever solve 3-SAT without the time blowing up exponentially. Nobody could prove it, but almost everyone believed it, and it became one of the foundations of modern computer science.
Researchers used it as a measuring stick. If you could show that solving some other problem quickly would also crack 3-SAT quickly, you had shown that problem was hopelessly hard too. Hundreds of papers, across scheduling, graphs, logic and much more, rest on this one assumption.
Now an internal AI model at OpenAI claims to have broken it. It says it found an algorithm that solves these puzzles meaningfully faster than the hypothesis allows, and it has checked the proof in a computer verification system called Lean.
And here is the remarkable part: the very people who proposed the hypothesis, Impagliazzo and Paturi, along with MIT's Ryan Williams, are now leading the public review of whether a machine has disproved their own idea.
So what happens next? If the disproof holds, a large part of theoretical computer science has to be revisited.
Every result that said "this problem cannot be solved faster, assuming ETH" loses its foundation, and researchers will have to work out which of those walls were real and which were simply where we stopped looking. It does not mean everything becomes easy. The new algorithm is still slow in absolute terms and this is not the famous P versus NP problem being solved.
But it means our map of what is possible was wrong in a place we were very confident about, and it was an AI that redrew it. If the disproof fails, the hypothesis survives and the field breathes out, but we will still have watched an AI produce serious, checkable work on one of the deepest questions in the discipline, closely enough that the founders of the idea had to take it seriously. Either way, something has shifted.
turned it into a proof of concept at permit.petercai.com/ courtesy of claude
Been dealing with annoying bots that constantly hammer my site, ignore robots.txt, disguise requests with unique ips+user agents per request, and no rate limiting. Rude
My agent figured out a way to permaban anything that fails a test it devised. Test details stay secret for now
This is amazing because there are thousands of responses and they’re all of the form “ACTUALLY what users want is [my specific concern]”
Product is just as hard as ever
Peter Cai retweeted
There's been a ton of talk about the role of humans in code review, and when and how humans should be signing off on changes.
I believe that, long-term, humans have no role in routinely reviewing code.
petercai.com/ai-makes-skepti… critical reading skills are more important than ever as the effort to generate persuasive writing supporting any position is being driven to zero
Leveling the playing field in writing has already led to unintended consequences; many more are on the way
There's the small matter of going from lockstep deterministic to server-authoritative game engine, but the hard part has been recreating every game rule precisely from youtube videos
there are so many of them, & the game was unusually polished - lots and lots of small flourishes
3DS shifts liability and is supposed to solve this but because its opt-in for US merchants, it carries negative signal and increases decline rates
Its still cheaper for many merchants to eat the extra fraud
good read on the complexities of scaling git writes
its always fun to see how much thought and effort really goes into making things work well, esp something many people use frequently without much thought
cursor.com/blog/git-at-any-s…
The makers were always going to be makers
AI lets them 20x their ambitions and now everything they make is better and more polished than it would otherwise be, for the same amount of effort
Doesn’t show up in measurements like gdp numbers though
To be honest with you all, Rails and Claude are making me feel like a fucking genius. Only in this moment, and it’s silly perhaps, and yet.
This is about our game-like pre-conference experience, clouds.sfruby.com/pier which was just an idea back on Monday. And these are not my ideas: @antiflasher designed 8-bit theme, @vmelnikova_en invented Cloud Cards, and @palkan_tula came up with the Pier, and it’s giving me so much joy being able to build it out, and implement team’s feedback.
Many things are hidden: Luma, where we sell conference tickets, sends us webhooks with ticket info, our Rails app processes them, sends email invitations, authenticates users with magic links, and when the person uploads their photo, we create their 8bit character, using RubyLLM and Nano banana. We place them on the pier and the game begins: you find yourself and complete other Quests, you collect Coins. Perhaps you’ll be able to use those coins at the conference to get things 🤓.
Most importantly: you discover who is coming: their interests, backgrounds. As more people join, you’ll get matched both on Pier and in real life at the event based on shared interests. And you already explore and learn about each other in the meantime.
For sure, @palkan_tula might come later with a refactoring (perhaps I rely on that for a bit!) but today I was able to build it exactly how I imagined it and it’s nothing short of true magic.













