3SUM and APSP and ETH, Oh My!

(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 AGOWhy 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 {\it 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…