(Throughout this post I will assume that the recent results by OpenAI and Anthropic contain correct proofs of what they claim.)
I wrote the following about 2 years ago but did not post it. It's dated, but that's the point.
BEGIN DOCUMENT FROM TWO YEARS AGO
Why do we think \(P\ne NP\)?
a) Lots of people have worked on SAT and other NP-complete problems, without getting them in P. This is not mathematical evidence but it is worth noting.
b) If SAT is in P then all problems in NP are in P. This implication is one reason I think \(P\ne NP\) is true. I find this more compelling than (a), though it's still not a proof.
c) Just my opinion: I think SAT is not in P.
-------------------------
3SUM is the following problem: Given integers \(a_1,\ldots,a_n\) is there a triple of indices \(i< j < k \) such that \(a_i + a_j + a_k = 0\)? There is a clever algorithm for this problem that takes \(O(n^2)\) time. It is conjectured that 3SUM has no subquadratic algorithm (that is, for every fixed \(\epsilon>0\) there is no \(O(n^{2-\epsilon})\) algorithm). (My spellcheck doesn't think subquadratic is a word. Are they right?)
This conjecture is widely believed. There is a notion of 3SUM-hardness and 3SUM-completeness. \( A \le B \) if there is a linear time function \(f\) such that \(x\in A\) iff \(f(x)\in B\). A problem \(A\) is 3SUM-complete if both \(A\le 3SUM\) and \(3SUM \le A\).
There are around 15-20 3SUM-complete problems. Either they are all subquadratic (which includes 3SUM being subquadratic) or none are subquadratic. Given the conjecture, none of them are subquadratic. That is the common belief.
Why do we think 3SUM has no subquadratic algorithm?
a) Lots of people have worked on 3SUM without getting it into subquadratic time. This is not mathematical evidence but it is worth noting.
b) Darn! There is no Cook-Levin-type theorem for 3SUM.
c) Just my opinion: I think 3SUM is not subquadratic. I only wish there were a Cook-Levin-type theorem for this belief. I doubt this is possible.
--------------------------
APSP (All Pairs Shortest Paths) is the following problem: Given a weighted graph \(G\), find, for all pairs, the cost of the shortest path. There is an \(O(n^3\)) algorithm for APSP. It is widely believed that there is no subcubic algorithm for APSP (that is, for every fixed \(\epsilon>0\) there is no \(O(n^{3-\epsilon})\) algorithm). This conjecture is widely believed. There is a notion of APSP-hardness and APSP-completeness. \( A \le B \) if there is a linear time function \(f\) such that \(x\in A\) iff \(f(x) \in B\). A problem \(A\) is APSP-complete if both \(A\le APSP\) and \(APSP \le A\). (My spellcheck doesn't think subcubic is a word. Are they right?)
There are around 15-20 problems that are APSP-complete. Either they are all subcubic (which includes APSP being subcubic) or none are subcubic. Given the conjecture, none of them are subcubic. That is the common belief.
Why do we think APSP has no subcubic algorithm?
(a) and (b) similar to that for 3SUM. I state (c)
c) Just my opinion: I think APSP is not subcubic. I only wish there were a Cook-Levin-type theorem for this belief. I doubt this is possible.
---------------------------
ETH (Exponential Time Hypothesis) Not only is 3SAT not in P but 3SAT on \(n\) variables requires \(2^{\Omega(n)}\) time. ETH is widely believed.
Informally, if ETH is true, and \(A\) is NP-complete by a linear reduction, then \(A\) requires exponential time. There are many such NP-complete problems.
(a) and (b) similar to that for 3SUM. I state (c)
c) Just my opinion: I think 3SAT requires \(2^{cn}\) time for some \(c\). I only wish there was a Cook-Levin-type theorem for this belief. I doubt this is possible.
END DOCUMENT FROM TWO YEARS AGO
Three of my favorite hardness assumptions had a bad month. I'm glad the Unique Game Conjecture was proven true so I am 1-for-4 rather than 0-for-3 (if it were still open) or 0-for-4 (if it was refuted).
1) Anthropic has obtained an \(O(n^{1.9992})\) algorithm for 3SUM. Darling thinks this result is hilarious.
A writeup of this by J. Alman and V.V. Williams is here.
2) Anthropic has obtained an \(O(n^{2.9995})\) algorithm for APSP with integer weights (with no negative cycles). Darling, thinks this result is hilarious. (Spell check thinks Antrhopic is a word. Are they right?)
The same writeup in item (1) also contains this result.
3) OpenAI has obtained a \(2^{O(n\log\log n/\sqrt{\log n})}\) algorithm for 3SAT Darling thinks this result is hilarious. I agree with her. (My spellcheck things OpenAI is not a word. Are they right?)
OpenAI's announcement is here.
Lance blogged about it here.
So now what?
0) All of these results are being looked at by experts.
1) 1.9992 is close to 2. And we still think 3SUM can't get that much better. could conjecture that, for every fixed \(\epsilon\), there is no \(O(n^{1.5-\epsilon})\) algorithm for \(3SUM\).
Assuming the conjecture, for every fixed \(\epsilon\), for every 3SUM-complete problem \(A\) there is no \(O(n^{1.5-\epsilon})\) algorithm for \(A\).
At least until AI gives an \(O(n^{1.499999}\) algorithm for 3SUM.
2) Similar for APSP and, say, \(O(n^{2.5})\).
3) ETH. Replace with the following: there exists \(0<c<1\) such that there is no \(O(2^{n^c})\) algorithm for \(3SAT\). Or something else like it.
4) We can Regard this as good news. All of those problems that are 3SUM-complete are now known to have subquadratic complexity. Similar for APSP and ETH. Yeah(?)
