This is crazy.
People used to think that 3SUM couldn't be solved in O(n^1.99999), but couple of weeks ago that conjecture was disproven by Anthropic's AI. They also disproved some related conjectures to other similar problems, but importantly they didn't disprove the Exponential Time Hypothesis (ETH). The conjecture states that no subexponential algorithm for 3SAT exists.
Today, ETH was disproven by openAI. See also this.
There is (was) an entire field of research, called fine grained complexity, that fundamentally is built on these these conjectures. This means that in half a month, an entire field of theoretical computer science has completely collapsed. This has been a funeral for an entire field of science.
The entire reason 3SUM was interesting was because people thought this conjecture to be true. With the conjeture being false, any research that assumed it is basically worthless. People were never interested in finding an algorithm for 3SUM. They just hoped there wasn't one.
A new algorithm for 3SAT is definitely interesting in its own right. But this is not the outcome that anyone had wished for.
Who knows, maybe $$$P = NP$$$.








Auto comment: topic has been updated by pajenegod (previous revision, new revision, compare).
Auto comment: topic has been updated by pajenegod (previous revision, new revision, compare).
Auto comment: topic has been updated by pajenegod (previous revision, new revision, compare).
Not to be a contrarian, but I think the concern that "fine-grained complexity...has completely collapsed" is both too overblown or too narrow.
The bigger concern would be that intellectual work for theoretical computer science could potentially be increasing devalued with the abilities of these models, so that the entire ecosystem of prestigious conferences/publications could collapse (I'm not saying it should/should not, I'm just saying that would be a bigger concern). And let's not even talk about future societal ramifications...
For fine-grained complexity, there is still a number of useful hypotheses, such as the Unique Games Conjecture (or should it now be called the Unique Games Theorem?), which was proven by OAI in the batch that you linked. Others have also mentioned online matrix-vector multiplication and 1-vs-2 cycles problem as examples of assumptions in more specific models.
All of this is to ultimately say yes, I agree with you that this is all crazy.
I recommend watching 3Blue1Brown's video on AI in math. It gives a very interesting perspective on what mathematics is even for. Theoretical CS is a branch of mathematics so this applies there too.
Anthropic seems to have independently arrived at the same result too: https://github.com/anthropics/formal-math
Now the mathematicians are going to say OpenAI stole all the prompts they sent to Claude
sorry12000
$$$ P = NP $$$ is definitely true.
Why downvotes? When AI proved $$$ P = NP $$$, everyone must upvote to me.
yeah, it definitely is. it's so much more cool than $$$ETH$$$ turning out to be true. what, do you want to live in a world where every new discovery is as mundane and expected as $$$P\ne NP$$$? $$$3-SAT$$$ being solved in subexponential time, who would've thought. and also, if I'm not mistaken, this probably means that a lot of other $$$NP$$$ complete problems can be solved in subexponential time, right?
also tagging Kaban-5 since we had an exchange about this the other day
Maybe Formatci was onto something...
Hi Görre! Like it or not, in the absence of any other measure of authority, rating on this platform serves as a proxy for trustworthiness and expertise. So I think that carrying a rank as high as yours comes with responsibilities. Many people here will blindly trust whatever a red handle says, which means we all have to weigh our words carefully.
Unfortunately, I think this post is highly misleading. I understand it was written in the heat of the moment (it really has been a wild month), but several claims here are false, or at least much stronger than the evidence supports. Spreading unverified claims from a position of authority isn't wise, so I want to push back.
First, the post treats fine-grained hypotheses as beliefs the whole field bet everything on. That's not how researchers use them. Take 3SUM: sure, many people expected it to hold, but I don't think there was ever a consensus, and I doubt many experts would have staked their reputation on it. In fact, the 3SUM hypothesis has already been refuted once before! It originally stated that 3SUM has no $$$o(n^2)$$$ algorithm. Then Grønlund and Pettie found one in time $$$O\big(n^2 (\log \log n)^2 / \log n\big)$$$, and the hypothesis was adapted to the weaker "no $$$O(n^{2-\varepsilon})$$$ algorithm" version.
There's an important distinction here that's easy to miss at first glance: these are hypotheses, not conjectures. A conjecture is something you believe to be true but don't know how to prove. A hypothesis is something to be tested! A statement whose proof or refutation would be a big deal either way. Fine-grained hypotheses work as barriers. A reduction from A to B says "if you want to beat the known bound for B, you'll have to beat A first." One indeed may read it as a conditional hardness result. But read differently, it's a consolidation of effort: it tells people stuck on hundreds of different problems that they're all hitting the same wall, so they might as well attack the wall directly. Arguably that consolidation is part of why these hypotheses eventually fell.
Second, the theorems don't go away. A reduction "faster A ⇒ faster B" is true whether or not A is hard. When the hypothesis falls, the reductions don't become worthless; they become algorithms. APSP is the best example: there's a whole class of problems proven subcubically equivalent to it, so a single faster APSP algorithm immediately improved the best-known bounds for dozens of problems.
Third, people very much were trying to find faster algorithms. Grønlund and Pettie's slightly-subquadratic 3SUM and Williams's $$$n^3/2^{\Omega(\sqrt{\log n})}$$$ APSP were celebrated results. Shaving even log factors off these problems was an active research direction.
Now, half-jokingly, let me do a line-by-line pass through your blog post:
It indeed is!
As discussed above, not exactly correct.
Being pedantic (sorry!), but technically they just claimed to refute ETH. Some papers from OpenAI's previous batch were later retracted, so it's worth waiting for verification. That said, this one does look correct so far.
Indeed, there is. "Was" is a bold claim, and nothing backs it up.
Not correct.
False.
Definitely wrong.
There is a grain of truth here but the truth is very nuanced. Making such a bold claim is very deceptive.
So wrong!
Meh. Maybe. Some? Mostly people wanted to know the answer.
It sure is!
For ETH, I agree that most researchers expected it to hold (see, for example, this if interested), so "not what most people expected" would be fair. But I don't see what wishing has to do with it. This is an exciting algorithmic development!
Who knows!
wow, it looks like $$$P\ne NP$$$ only has a $$$10\%$$$ higher chance of being true than $$$ETH$$$. given that $$$ETH$$$ is known to be false, there might only be a $$$10\%$$$ chance that $$$P \ne NP$$$ now. or I should say $$$\Omega(10\%)$$$ chance, since it might be the case that not all of that $$$70\%$$$ loss can be applied to $$$P \ne NP$$$.
Actually, according to conditional probablity formula, The true chance of $$$P\ne NP$$$ is only $$$\frac{1}{3}$$$ now.
This is a red herring, the retracted papers didn't come with lean formalisations, and this one does (in fact, it has two independent formalisations!).
Thanks, I just sold all my Ethereum