Rendered at 21:07:53 GMT+0000 (Coordinated Universal Time) with Cloudflare Workers.
svat 19 hours ago [-]
While this has no immediate bearing on P-vs-NP, it is interesting to note:
- Early CS researchers like Donald Knuth entered CS in the days when regularly someone would come up with a surprising faster algorithm for some problem, and their intuitions were that most problems had faster algorithms than you'd expect.
- Later generations of CS researchers, as all the easy algorithms were discovered, and post Karp's definition of NP-completeness (and the Garey & Johnson book, say), began to specialize in proving hardness, and complexity theory with a “zoo” of complexity classes became more about separation and lower bounds, e.g. I've seen algorithms like Arora's PTAS for Euclidean TSP being described as a “failed attempt to prove a lower bound”. So an entire generation of researchers' intuition was mostly in the direction of an elegant universe with neat separation results (even if we couldn't get them).
- So e.g. surveys of computer scientists showed most of them believing that P≠NP, and someone like Knuth has always seemed a bit of an outlier for saying that maybe P=NP: his argument was simply that there are so many possible polynomial-time algorithms that we haven't explored, and maybe one of them with a large exponent could solve NP-complete problems. (In response to arguments that many researchers have failed to find any such algorithms, he would say that many researchers have failed to prove that P≠NP.) E.g. in 2017 when Scott Aaronson wrote his survey (https://www.scottaaronson.com/papers/pnp.pdf = https://www.scottaaronson.com/papers/pnp-kindle.pdf) he wrote:
> Admittedly, it can be hard to tell whether declarations that P = NP are meant seriously, or are merely attempts to be contrarian. However, we can surely agree with Knuth and Lipton that we’re far from understanding the limits of efficient computation, and that there are further surprises in store.
- What we've seen in this month is surprising unexpected algorithms, like o(n log n) algorithms for FFT and integer multiplication, and now this sub–exponential-time algorithm for 3-SAT. (Yes the ETH has had less support than P≠NP but I still gather it's unexpected.)
So (though I don't expect intuitions on P≠NP to change, and probably that's still the right intuition… but I'm just an interested amateur), maybe there will be a bit of a swing of the pendulum back to the idea that maybe clever algorithms exist that we just haven't thought of.
Animats 18 hours ago [-]
There are hard problems where the worst case may be exponentially hard, but the average case is much faster. Linear programming and the traveling salesman problem are like that. The faster approaches are considered "probabilistic solutions".
In cryptography, most of the problems believed to be exponentially hard, such as factoring, don't have proofs of an exponential lower bound. There's some risk of a breakthrough that makes those problems easier. A probabilistic solution would be good enough to break many cryptosystems.
I suspect that people at the cryptanalysis agencies worldwide are staying up late tonight, trying to figure out the impacts and risks of this new result.
vlovich123 16 hours ago [-]
Funny you mention probabilistic algorithms. If I’m not mistaken one of the OpenAI results is that most of the probabilistic methods (specifically those that use a logarithmic amount of space)-4 have non-probabilistic versions that are as efficient in time and space (L = RL = BPL)
robryk 10 hours ago [-]
> most of the probabilistic methods (specifically those that use a logarithmic amount of space)
These are by far not most, nor most of the practically useful ones. Directed graph reachability, given an adjacency list as input, is NL-hard.
> In fact, one of the first things I wanted OpenAI to check is that no existing cryptosystems are compromised by the result. Apparently they are safe...
so if you trust his trust of OpenAI, then this has no (immediately obvious) bearing on cryptosystems for now.
luma 11 hours ago [-]
Somehow, their wide range of results touch every single area of math except anything touching cryptography. I think it's fair to expect that three letter agencies are given the ability to veto the publication of certain discoveries.
tomaskafka 10 hours ago [-]
Just like when the Manhattan project could be recognized by all the nuclear scientists stopping publishing.
w4der 9 hours ago [-]
Wasn't there a comment a while ago when all major LLM providers went down almost at the same time that it was caused by a sort of virtual "Room 641A" thing?
Animats 17 hours ago [-]
Not by this result. But it opens up a new area of problems to hammer on that might get somewhere.
marcus_holmes 12 hours ago [-]
Seeing the panicked state of the PHP ecosystem at the moment, and having worked in the financial system in the past, I dread the thought of what would happen to global banking if a frontier model broke a maths problem that underpins our crypto systems...
16 hours ago [-]
FlyingCanoe 16 hours ago [-]
For linear programing, the interior point method has a polynomial worst case.
It also not probabilistic, so linear programing is not rely a good example
m-chrzan 10 hours ago [-]
Given the context, Animats probably was speaking of integer linear progamming, which is NP-complete.
caughtinthought 12 hours ago [-]
And interior point is regularly outperformed by an exponential time algorithm (simplex) lol
LPisGood 6 hours ago [-]
Linear programming admits a worst-case polynomial time algorithm.
It is notable that simplex, especially dual simplex is often better in practice, especially for integer linear programming with branch and bound because you only have to slightly modify the parent optimal basis in simplex vs entirely restarting or refactorizing for interior point methods.
williamstein 5 hours ago [-]
> In cryptography, most of the problems believed to be exponentially hard, such as factoring, don't have proofs of an exponential lower bound.
There are subexponential algorithms for integer factorization, e.g., the general number field sieve and Lenstra’s ECM.
marcosdumay 5 hours ago [-]
With about O(2^(n/log(n)) instead, I imagine those people are deeply interested on the impacts, but nobody will be losing their sleep.
wslh 6 hours ago [-]
> In cryptography, most of the problems believed to be exponentially hard, such as factoring, don't have proofs of an exponential lower bound.
Actually, integer factorization already has subexponential-time algorithms, such as the General Number Field Sieve (GNFS).
Ar-Curunir 10 hours ago [-]
ETH has no impact on most of cryptography, as it was never based on NP-hardness in the first place.
slashtrends 19 hours ago [-]
Part of the problem with the current centralization of the world's math capability within AI labs is that if they do find that P=NP via an efficient algorithm, it could have implications on all modern public key based cryptography. So it's not completely clear that they will (be allowed to) release these results.
devy 18 hours ago [-]
> if AI frontier labs do find that P=NP via an efficient algorithm, it could have implications on all modern public key based cryptography.
The fact that other math problems are bulk solved yet nothing from cryptography was released/published as solved could be a strong indicator that "all modern public key based cryptography" could have been at risk.
hathawsh 18 hours ago [-]
Or it could indicate that more resources have been put into cryptography than most other math fields, so AI hasn't yet caught up to our progress.
freehorse 6 hours ago [-]
Also most of the results come from "spray attacks". In addition to the results that are found there are also tons of failed attempts on other problems. So merely through how large the whole space is one should not necessarily expect groundbreaking results in cryptography specifically (even though it can also be true that some results be withheld, at the same time).
murderfs 16 hours ago [-]
It seems rather unlikely that solving the Navier-Stokes problem is harder than e.g. a better attack on a reduced-round AES. Perhaps they think an epsilon improvement in the exponent isn't worth publishing, but it seems more likely that they're intentionally withholding any results they have.
bscphil 10 hours ago [-]
Maybe I'm misunderstanding you, but a better attack on a reduced-round AES has been achieved by LLMs. Anthropic did it and published it already, a chosen plaintext attack that improves on state of the art against reduced-round by "200-800x". https://anthropic.com/document/aes_mobius_bridge.pdf
treebeard901 14 hours ago [-]
It's a reasonable assumption that the cases where the NSA, etc, had a role in designing cryptographic systems, and reportedly made specific suggestions that could be forms of a backdoor, would all be revealed by AI being tasked to find it. Maybe even indirectly as part of the broader defensive security research by models unreleased to the public. If algorithmic complexity or a really obscure backdoor has existed in cryptographic systems and put there by the Gov't, it seems that current frontier models would have the best chance of revealing it.
Maxion 14 hours ago [-]
Either that or they've not put the model(s) on those problems. Remember that even the Navier-Stokes solution did use a large amount of compute. I'm not sure they'd even want to waste it on problems that they can't get PR from.
freehorse 6 hours ago [-]
The issue is that if a country's agencies find an efficient attack to modern public key based cryptography with LLMs, there is no reason to think that other countries will not find the same in a few months with their LLMs. So, finding a vulnerability could offer a short term advantage, but one would want eventually to protect their own, too.
Someone 12 hours ago [-]
> The fact that other math problems are bulk solved yet nothing from cryptography was released/published as solved could be a strong indicator that "all modern public key based cryptography" could have been at risk.
“Could be”, but I think the correct way to describe it is “the general public doesn’t know”. It could be any of
- they tried very hard without finding weak spots
- they tried for a while, and gave up because the LLMs didn’t even produce leads
- they tried, found something and kept it for themselves
I think the first is not unlikely. Before LLMs, the likes of the NSA must have looked really hard into these problems, and IMO it’s not likely they found something substantial (if they did, their counterpoints in other large countries likely would find it, too, and some of them would have used that knowledge)
orangecat 3 hours ago [-]
"They've specifically avoided trying" is also a possibility. Because what do they do if they actually find a critical flaw? Publishing leads to mass chaos. If they don't publish but it leaks, also mass chaos. (Probably just leaking the existence is enough without the actual proof). If they're "responsible" and report it to NSA, there's a good chance that model development gets forcibly halted and some chance that the entire company gets seized on national security grounds.
sampo 17 hours ago [-]
> it could have implications on all modern public key based cryptography
I think a proof of P=NP via a galactic algorithm is far more likely than a proof of P=NP via an efficient algorithm.
I mean if someone develops an O(n^100) algorithm for solving an NP-complete problem, that would prove P=NP, but pose no immediate threat to cryptography.
It increases risk, in that a galactic algorithm increases the odds that an efficient algorithm exists waiting to be found, but it is entirely (epistemically) possible that the galactic algorithm exists but the efficient algorithm doesn't.
fpoling 16 hours ago [-]
And vise versa, a proof that P!=NP do not exclude an algorithm that is fast enough for practical n.
Dylan16807 14 hours ago [-]
Maybe, but that feels significantly more exotic and unlikely to me. You have to basically negate the natural cost scaling of brute force in the thousand to million n range but lose that speed benefit later.
skissane 11 hours ago [-]
Well, if someone found a quasipolynomial time algorithm – O(n^log(n)) – for an NP-complete problem, that would technically be compatible with P!=NP, but might have quite significant practical implications.
mattm 17 hours ago [-]
The 2012 movie "Travelling Salesman" is a thought provoking film that explores this scenario.
squidmaster 11 hours ago [-]
[dead]
dingdongditchme 14 hours ago [-]
I believe this stems from an incomplete understanding of the problem space on my part (excuse the multiple puns); but, I am skeptical Knuth really said P=NP. There are so many mathemtical examples of equations that clearly show P≠NP. Computing in itself was originally formed from using iterative methods to solve hard problems. Least-squares methods, sin() cos(), traveling salesman, so many to list? To say P=NP for all problems seems like a fools errand to me.
vanderZwan 13 hours ago [-]
See his answer to the seventeenth question in this interview:
> Don Knuth: As you say, I've come to believe that P = N P, namely that there does exist an integer M and an algorithm that will solve every n-bit problem belonging to the class N P in n**M elementary steps.
dingdongditchme 2 hours ago [-]
thanks for the quote. Reading through it is clear that my understanding of P=NP is not complete enough. I would have thought n*M is precisely not polynomial but exponential time.
kscarlet 13 hours ago [-]
Do you understand what P and NP mean?
dingdongditchme 2 hours ago [-]
I am not a computer scientist so my understanding is "incomplete". I thought it stood for polynomial and non-polynomial time. But i do mix them up here and there. What i have read time and time again is that: If P≠NP would mean some problems really are harder to solve than to check (which feels intuitive given working encryption exists and all the mathematical functions that I know and understand). For example checking the roots of polynomials is easier than finding them in the first place.
Ohentis 19 minutes ago [-]
From this comment it isn't clear if you previously thought it stood for polynomial and non-polynomial and have been corrected or if you still have this misconception, but just in case: it actually stands for polynomial and nondeterministic polynomial. P is a subset of NP, they aren't opposites. And yes most people intuit that they likely aren't equal.
zahlman 14 hours ago [-]
We had O(n lg n) since 2019 already; now we (supposedly) know the limit is less than that (but of course at least linear).
> In 2019, Harvey and van der Hoeven came up with a galactic algorithm with complexity O ( n log n ) {\displaystyle O(n\log n)}. This matches a guess by Schönhage and Strassen that this would be the optimal bound.
> In September 2026, OpenAI released a preprint claiming an algorithm with complexity O ( n ( log n ) α ) {\displaystyle O(n(\log n)^{\alpha })} with α < 1 {\displaystyle \alpha <1}
This is an amazing and unexpected result. To be clear though, it does not imply that NP is subexponential: "Note that runtime bounds of the form 2^o(n) do not transfer under general polynomial-time reductions (2^n^o(1) would be needed for this), so our result does not imply that general NP problems
admit subexponential time algorithms."
Edit: To explain more, it is guaranteed that you can reduce any NP problem to 3SAT in polynomial time with a polynomial factor in input size. You still have to solve it.
If 3SAT were solvable in polynomial time, then polynomial(polynomial(x)) = polynomial(x) and you're implied to have an overall polynomial time solution.
But what we have here is that 3SAT is solveable in subexponential time. subexponential(polynomial(x)) is not guaranteed to be sub-exponential.
Further edit: The subexponential solution does carry over to any (?) problems that have can be reduced to 3SAT in a linear number of variables. They list: Counting independent sets, Counting proper q-colorings, Counting perfect matchings.
marshray 20 hours ago [-]
> The subexponential solution does carry over to any (?) problems that have can be reduced to 3SAT in a linear number of variables. They list: Counting independent sets, Counting proper q-colorings, Counting perfect matchings.
Wouldn't that also include functions that can be evaluated in hardware using a fixed number of gates? E.g., symmetric cryptography?
pcbouman 17 hours ago [-]
A circuit with a fixed number of (binary logical) gates can be solved in constant time, as it will have a fixed number of input bits, so brute force will have a fixed number of input options to consider. This does apply to cryptographic algorithms with a fixed key size, like the ones used in practice, as well.
The whole point of computational complexity is to look at the scaling behavior when you increase the inputs/key size/size of the circuit.
ReptileMan 13 hours ago [-]
From my reading no. Because brute forcing anything symmetrical is already O(n). What protects us is the assumption that there is not enough energy in the observable universe to brute force 2^256 key.
LPisGood 19 hours ago [-]
> To be clear though, it does not imply that NP is subexponential
Is there a subset of NP problems for which a subexponential algorithm would witness the entire NP class being subexponential?
eli_gottlieb 18 hours ago [-]
~~Yeah, that's NP-complete problems.~~
EDIT: DISREGARD THAT I WAS MISTAKEN
csheehan10 18 hours ago [-]
It's NP-complete problems if "subexponential" means O(2^{n^{\epsilon}}) for every \epsilon>0.
If subexponential just means 2^{o(n)}, (as it is here, O(2^{n/\sqrt{\log n}})), then no. E.g. if the cost of the reduction took you from n to \sqrt{\log n}n, then you'd be back to exponential time. The Subexponential Reduction Family is the class of problems that preserve subexponential time in the second sense.
LPisGood 18 hours ago [-]
That is unfortunately not the case
13 hours ago [-]
demibabs 21 hours ago [-]
Can you explain more?
triMichael 21 hours ago [-]
After some back and forth with AI, I think I understand:
1. The Exponential Time Hypothesis being false shows that 3SAT specifically is sub-exponential time
2. Any NP complete problem can be changed into 3SAT in polynomial time
Put these two together and you would think that they would mean that any NP complete problem can be solved in sub-exponential time. But this isn't necessarily true because changing the NP complete problem into 3SAT can increase the number of variables, which can theoretically negate the sub-exponential time.
demibabs 21 hours ago [-]
Oh ok, I understand what you mean.
(By the way, I think you mean NP-complete, not NP-hard. The Halting Problem is NP-hard.)
edanm 14 hours ago [-]
The halting problem is NP hard, technically speaking, but it's much harder than that - it's uncomputable. I don't think it's common to refer to it as NP-hard because it's confusing.
isaacfrond 10 hours ago [-]
Right. To be clear: the halting problem is not in the class NP. Any problem in NP can trivially be reduced to the halting problem and so the latter is NP-hard.
triMichael 21 hours ago [-]
Thanks for the correction! I updated my answer to fix that :)
bobmarleybiceps 20 hours ago [-]
oh that actually helps a lot. I was tying myself in knots trying to think it through.
sourdecor 19 hours ago [-]
"Any NP complete problem can be changed into 3SAT in polynomial time" - if I remember correctly, turning an NP-complete problem into 3SAT is not part of the problem statement - it just means that when working with NP-complete problems, they are always translated to 3SAT first, and whenever someone is trying to prove something they are working against 3SAT.
gbacon 1 hours ago [-]
The class NP-complete contains the hardest problems in NP. If you pick any problem in NP-complete, all problems in NP can be reduced to it (meaning that a solution to the problem you chose can be used to solve everything in the rest of NP) in polynomial time or “efficiently.” This applies to all of NP, including every other NP-complete problem, so in a sense, NP-complete problems are the same problem dressed in different clothing.
So the reduction to 3SAT could happen in principle, but it isn’t a necessary step.
imadr 21 hours ago [-]
P=NP -> 3SAT has a polynomial time algorithm
P=/=NP -> 3SAT has no polynomial-time algorithm
ETH is true -> 3SAT has no subexponential time algorithm
ETH is false -> 3SAT has a subexponential time algorithm
------
ETH true -> P=/=NP
ETH false (!!!) -> P ?= NP remain unsolved
demibabs 21 hours ago [-]
No I get that, but I don't get how proving 3SAT can be proved in subexponential time does not imply all NP-complete problems can be as well, since they can all be reduced to 3SAT in polynomial time.
Aunche 21 hours ago [-]
Suppose 3sat is solved in 2^sqrt(n). That's subexponential. An n^2 reduction from sat to 3sat is polynomial. However, an algorithm using this reduction with the discovered solution, would run in (2^sqrt(n))^2 which is just 2^n.
That last statement is not correct. (2^sqrt(n))^2 equals 2^(2 * sqrt(n)). If you just take n=1 in your expression you can see the error, your (2^sqrt(n))^2 yields 4, while 2^n is just 2.
Dylan16807 14 hours ago [-]
Yeah but you're fixing the wrong thing. The problem after reduction to 3sat is (2^sqrt(n^2)). The altered n becomes the input to 3sat.
I was just correcting the statement as written. I see they meant to say something else. You are correct about my other comment--I was in a misdirected, math-correcting rage.
jballanc 19 hours ago [-]
...that's...not how exponents work
Dylan16807 15 hours ago [-]
The result is right, they wrote the parentheses in the wrong spot, don't be so shocked.
nightshade1511 21 hours ago [-]
Suppose 3SAT can be solved in 2^(n^0.9) time (this is not the actual bound in paper). And another NP problem can be reduced to 3SAT in polynomial time, but the reduction increases the problem size from n to n^2. Then after the reduction the other NP problem can solved in 2^(n^1.8) time, so it does not mean all np problems are sub exponential.
raegis 18 hours ago [-]
Hey, this is a common error. (2^(n^0.9))^2 is not 2^(n^1.8) but 2^(2 * n^0.9).
raegis 5 hours ago [-]
Apologies, I'm incorrect. I misread your math.
11 hours ago [-]
11 hours ago [-]
caughtinthought 21 hours ago [-]
Basically 3SAT algo isn't sub-exponential enough to absorb the arbitrary poly cost for the reduction
So 3SAT+poly reduction ends up being exponential
demibabs 21 hours ago [-]
Gotcha, thanks
csheehan10 17 hours ago [-]
To achieve this you would need to show that 3SAT is solvable in 2^{n^c} time for every c>0, not just a single c<1.
In this case they have c = 1-0.5(\log \log n)/(\log n) which is approaching 1 for large n.
imadr 21 hours ago [-]
Misunderstood your question sorry, I have no idea!
20 hours ago [-]
vote_farisa_202 21 hours ago [-]
The algorithm's runtime is in faster growing than O(exp(n^a)) for any a < 1. It's not subexponential in the sense that factoring is, which I believe has a secondary exponent of 1/3 under the best algorithms.
It's still a big result, but it's mostly theoretical. It might help explain, structurally, why most SAT instances are far easier than an exponential model would indicate.
calf 21 hours ago [-]
For example, a 2^√n subexponential algorithm then used on an input after a n^2 polynomial reduction from some other NP-complete language incurs a total running time of 2^√(n^2) = 2^n, which again is exponential.
shoo 20 hours ago [-]
Yep! Or for a slightly generalised example, if we pick our sublinear function of n to be n^(1-epsilon) for some small epsilon > 0
then 2^(n^(1-epsilon)) belongs to 2^o(n)
Suppose p(n) is some polyonomial in n, our polynomial reduction. Let's make it a monomial for simplicity, p(n) = n^a
Does 2^(p(n)^(1-epsilon)) necessary belong to 2^o(n)?
No, that only holds if (n^a)^(1-epsilon) = n^(a (1-epsilon) ) < n^1 . So, it fails for p(n) = n^a for any a such that a >= 1/(1-epsilon)
gewetensleegte 12 hours ago [-]
> To explain more, it is guaranteed that you can reduce any NP problem to 3SAT in polynomial time with a polynomial factor in input size.
No, subexponential is not the same as polynomial time. There's sub-exponential functions that grow faster than polynomial.
tomaskafka 10 hours ago [-]
I feel this comment not getting enough attention and this seems like an appropriate place to quote:
> Somehow, their wide range of results touch every single area of math except anything touching cryptography. I think it's fair to expect that three letter agencies are given the ability to veto the publication of certain discoveries.
Maybe because cryptography is funded better than the rest of math.
The big AI companies spend millions on some of these proofs (15M was one estimate for the Naiver-Stokes thing). Had anyone has spent millions on them before this? There was a 1M prize but that certainly wouldn't convince anyone to spend orders of magnitude more to solve the problem.
Meanwhile the three letter agencies are spending billions on cryptography. They have programs that recruit students starting in high school. So maybe they are sending the spooks to suppress OpenAI's cryptography breakthroughs, or maybe they just already outspent them.
That to me is the point that isn't getting enough attention: pure math isn't that well funded. I agree as much as anyone that these proofs are an unprecedented breakthrough for LLMs, but let's keep in mind that the money they are throwing around is also unprecedented.
snowwrestler 10 hours ago [-]
I don’t think that’s fair, it does not usually work that way in private industry.
It’s possible they have major findings in crypto but are coordinating disclosure. The PHP bug was worked for months and only leaked a few hours early.
It’s also possible they have not found any major flaws yet. The math underlying major cryptography libraries is way simpler than these advanced proofs, and the implementations among the most scrutinized and hardened bits of code in the world.
The PHP bug paradoxically gave me hope. It was not magic; it was a logic flaw that was already known for years. And exploiting it has proved way more difficult than initially feared.
paxy 8 hours ago [-]
This very proof we are discussing is at the very heart of cryptography. People have no idea what they are talking about.
brookst 9 hours ago [-]
This is the “absence of evidence is proof of existence” mindset.
tomaskafka 8 hours ago [-]
It is, but it is also how the Manhattan project became "visible" to intelligence community - scientists related to nuclear research stopped publishing papers.
fxwin 7 hours ago [-]
it's not proof of existence, but it's suspicious unless there is a good reason why cryptography should be more immune to AI driven progress than other disciplines.
If i knew an elephant had walked through my porcelain store, and miraculously all the blue cups survived intact while every other type of cup was smashed to pieces, I'd guess that someone took steps to preserve them.
seizethecheese 3 hours ago [-]
I think the premise is interesting (that there are no breakthroughs in cryptography) but does not support the conclusion (that therefore three letter agencies are suppressing this).
I think the premise does support the conclusion that there's some mechanism suppressing release, though.
8 hours ago [-]
baoooooooooooo 7 hours ago [-]
I think simple market forces explain the omission of any discoveries relating to cryptography, the labs have an obligation to at least build solutions and make them available before releasing findings.
If I were to start inferring what’s going on, it’s that findings in this space have relevance to breaking current weak cryptography.
dachtovyvse 9 hours ago [-]
I remember (if that is not a false memory) that Sarnak once expressed the opinion that factoring has polynomial complexity.
The proofs themselves are far beyond me, but the first page of the Anthropic paper, at least, is much easier for me to follow than the OpenAI one.
hurfdurf 9 hours ago [-]
Didn't Anthropic also come out with a paper just hours after OpenAI did, a couple weeks ago during that Navier-Stokes thing? Once is coincidence...
criemen 22 hours ago [-]
Wow. Complexity class separations are really really rare.
Can an expert in sat solving comment if there's any immediate applications of the method from the paper? Or is SAT solving in general pretty far away from worst-case times, and this is a theoretical algorithm which would be hard to apply in practice.
bsubs 21 hours ago [-]
SAT-solving expert here. No immediate applications (the results in the paper are "galactic"). The main question is whether some ideas here will snowball into other ideas, one of which could eventually be very practical.
sebmellen 20 hours ago [-]
This is a complete non-sequitur, but I checked out your web page. I love the Curious George image. My daughter has been deeply into the Curious George episodes for the past couple of months, and I don't think I've seen him show up in many other places besides kids' shows :D
angry_octet 13 hours ago [-]
I think of Curious George Goes to a Chocolate Factory when I fire up Claude Code.
chr15m 20 hours ago [-]
Such a good show. My kids grew up on it!
ashkankiani 20 hours ago [-]
What do you mean by "galactic"?
yyyk 20 hours ago [-]
Galactic algorithms have such huge constants they figuratively need a galaxy-sized computer and/or galaxy-sized problem, to have any advantage over the normal solutions. Imagine a generic sorting algorithm in O(n) that had a constant of 10^92 **. Technically superior but in practice unusable.
** Yes, I know that's proven to be impossible.
MichaelDickens 20 hours ago [-]
There are realistic situations where galactic O(n) sorting algorithms exist, right? 32-bit integers can be sorted in O(n) using 2^32 words of memory, using bucket sort[1].
If objects have a maximum size of 4 GB (= 2^35 bits), then arbitrary objects can be sorted in O(n) using 2^2^35 bits of memory.
Right, that's why I wrote "a generic sorting algorithm". Your case adds the integer limit which allows it to avoid O(nlogn) minimum.
adrianN 17 hours ago [-]
You can use Radix sort https://en.wikipedia.org/wiki/Radix_sort to lower the memory requirement for limited bit-width integers. But there are more practical o(n log n) methods for sorting integers.
adgjlsfhk1 17 hours ago [-]
Well optimized radix sorts are actually pretty fast (assuming you have the proper fallbacks to quicksort/insertion sort to deal with medium/small sizes)
> A galactic algorithm is an algorithm with state-of-the-art theoretical (asymptotic) performance, but which is not used due to practical constraints.
Yes, I think we can pretty safely say that the algorithm in the paper is not used due to practical constraints. This is a subjective judgment, but pretty clear from the paper that the algorithms aren't practical to apply.
infamouscow 21 hours ago [-]
The data you put into a SAT solver has substantial effect on it's performance in practice. Real world inputs tend to be much nicer than pathological ones, so I don't think there's much practical application, but I also haven't read the paper yet.
kingstnap 21 hours ago [-]
I also haven't read ths paper but coding agents absolutely are a part of modern SAT solver coding challenges.
spr-alex 4 hours ago [-]
The bounds where this subexponential claim kicks in is at n > 2^10^9. The information to describe such a large 3-SAT would not fit inside of a blackhole 10^1000 times the size of our whole universe. At this incredible scale, the philosophy of computational analysis might be open to loopholes that autogenerated / autoresearch is subtly exploiting instead.
strommec 21 hours ago [-]
It's surprising that Exponential Time Hypothesis would be false. Quoting a paper from 2022[1]:
> We prove that the time complexity of self-attention is necessarily quadratic in the input length, unless the Strong Exponential Time Hypothesis (SETH) is false[...]
If OpenAI's proof is correct, does that mean self-attention can be implemented in sub-quadratic time? I.e. we could eventually have all the most advanced LLMs running on cheap hardware? To put it more playfully, is ETH being false actually bearish for Nvidia?
No, SETH implies quadratic time does not mean !SETH implies !quadratic time.
dnautics 21 hours ago [-]
but you're telling me.... there's a chance
Xirdus 21 hours ago [-]
This but unironically.
programjames 21 hours ago [-]
put a number on your probabilities. there's a chance you have an aneurysm in the next few minutes and fail to see my comment. if so, oh well, i tried.
_ink_ 12 hours ago [-]
If AI really scales indefinitely is an increase in efficiency even bearish for Nvidia? Wouldn't they still build more and more compute as fast as they can, because these things get smarter and better with more compute?
caughtinthought 21 hours ago [-]
SETH is a much stronger claim than ETH
jibalt 19 hours ago [-]
Not relevant, because !ETH => !SETH
What is relevant is that the logic goes the other way: SETH implies quadratic, !SETH implies nothing.
varyherb 19 hours ago [-]
Right, so a refutation of ETH would also refute SETH.
margalabargala 20 hours ago [-]
Yes, it's one strong stronger.
refulgentis 20 hours ago [-]
It's playful!
But it's also not even wrong, in the Pauli sense.
That makes me wonder if "I see your CS proof, how does this affect LLMs / nvidia stonk price???" being immediately self-described as "playful" ensures criticism looks cranky.
Joker_vD 16 hours ago [-]
"I see your particle physics paper (on sustainability of neutron-induced chain fission reaction in uranium), how does this affect the world politics???"
Turns out, it affected the global politics tremendously.
bananaflag 15 hours ago [-]
Anthropic also claims a disproof of the ETH, posted here:
I wonder how long it'll pay for frontier labs to use compute this way?
I'm reminded of the Apollo program that was cool for a while, but eventually the public lost interest.
Maybe it becomes cheaper? Maybe other labs want to prove their worth will pick up the slack when another loses interest?
adgjlsfhk1 20 hours ago [-]
the presumption is that these results are a side-effect of reinforcement learning to make the models smarter.
paxy 19 hours ago [-]
Uh no, reinforcemnt learning doesn't magically pop out math proofs. OpenAI has a ton of mathematicians on staff and is spending millions of dollars in compute to pursue these solutions.
baq 16 hours ago [-]
Dropping ultra hard problems on those things and giving them reward when lean accepts the proof sound like an obvious RL environment tbh
geraneum 12 hours ago [-]
Then anyone with access to their api’s could’ve come up with these already.
mark_something 10 hours ago [-]
If someone wants to throw enough money at doing that. Solving the Navier-Stokes problem cost a few million dollars. I don't know how much the other problems cost but I suspect they're all above $100.000.
squidmaster 11 hours ago [-]
[dead]
Philpax 19 hours ago [-]
That's not necessarily incompatible. The raw output could come from RL rollouts where the model learnt from the process of solving these problems.
TheImmortalPyth 2 hours ago [-]
[flagged]
qgin 21 hours ago [-]
NP looking a little more P than usual
jibalt 19 hours ago [-]
No, this doesn't touch NP ?= P
pxx 17 hours ago [-]
ETH (which was commonly thought to be true) implies P≠NP.
sure, this proof itself doesn't settle the P/NP problem, but we've lost one of our core beliefs.
jibalt 16 hours ago [-]
I think that statement is too strong -- if ETH was a core belief then its implication P≠NP must also have been a core belief ... but I don't think that those who assumed ETH held it that strongly. As you say, it was commonly thought to be true ... as was P≠NP ... and the latter still is. But is not a "core belief" -- I think virtually everyone believes that they could be wrong, whichever side they're on.
caughtinthought 12 hours ago [-]
I mean P!=NP kind of is a core belief
mathgladiator 19 hours ago [-]
At this point, I have no expectations. The future is alien and strange, so time to talk the silicon runes...
20 hours ago [-]
mlmonkey 22 hours ago [-]
Can someone ELI5 ETH for those of us who slept through theoretical CS classes? Asking for a friend...
In computer science, the satisfiability problem is the task of determining whether a boolean problem can be satisfied, that is, made to be true, by some combination of inputs. For example, the expression: A AND NOT B is satisfied whenever A is true and B is false, while the expression: A AND NOT A cannot be satisfied.
A naive approach to satisfiablilty would be to check every possible input and see if the expression evaluates to true.
However, the number of combinations that must be checked is 2n, where n is the number of variables in the expression. This is what is meant by exponential time.
The exponential time hypothesis conjectures that you cannot do better, that is, the number of operations needed to solve satisfiability will always be exponential in the size of the problem, no matter what algorithm is chosen.
If this hypothesis is true, it would imply that P≠NP, because satisfiability has been shown to be in NP, and in order for it to be in P there would have to exist an algorithm that solves it in polynomial time.
gberger 21 hours ago [-]
2n should read as 2^n
newsy-combi 21 hours ago [-]
Unless OP already solved p=np...
pvab3 20 hours ago [-]
that threw me, thanks
22 hours ago [-]
nullc 21 hours ago [-]
> the number of operations needed to solve satisfiability will always be exponential in the size of the problem, no matter what algorithm is chosen
A common complexity theory misunderstanding is that statements like this applies to all or even most instances-- and it leads to objectively bad engineering of the form "oh look this is actually 3sat, it's unsolvable".
(Great fodder for a midwit meme: idiot and genius say "my heuristics go brrr!"-- midwit says "No no no! NP problems can't be efficiently solved!")
Any specific instance may be efficiently solvable (and perhaps all instances coming from your particular problem set -- a subset of all possible 3sats).
So I would add to that paragraph "at least for some 3sat instances".
marshray 20 hours ago [-]
My 2nd grader once brought home a homework sheet with some simple problems involving combinations of coins and I was like "this is unsolvable!"
21 hours ago [-]
SyzygyRhythm 21 hours ago [-]
There's a set of problems that are (it is conjectured) easy to verify but hard to solve. One of them, called 3SAT, looks for values (a, b, c, ...) such that an expression like ((a or b or c) and (b or not-c or e) and ...) evaluates to true. And it turns out that all of these supposedly hard problems can be converted to 3SAT, so if you find a solution to one you find a solution to all.
The Exponential Time Hypothesis in effect says that 3SAT can only be solved by brute force--trying every possible combination until you find the right one. If your 3SAT expression has 100 variables, then this will take about 2^100 tries (exponential time).
What they found was an algorithm faster than brute force. 3SAT is still potentially one of these hard problems, but finding anything faster than brute force is a major advance.
pcstl 22 hours ago [-]
The exponential time hypothesis is essentially that NP-complete problems' best solutions are all exponential.
NP-complete problems are essentially those where you need to make some kind of choice over a superlinearly-growing set of options where each option can be solved in polynomial time. Like, for example, finding a route between cities on a map under a certain total distance. You might need to go over all choices of routes.
The ETH essentially assumes that the best solution (in terms of complexity, i.e. how it grows) you can get for these kinds of problems is exponential. OpenAI just proved that this is false, you can have solutions that are below exponential complexity (but still above polynomial - if anyone finds a polynomial solution then we'd have proven that P=NP)
eru 21 hours ago [-]
> NP-complete problems are essentially those where you need to make some kind of choice over a superlinearly-growing set of options where each option can be solved in linear time.
Seems like a weird way to describe NP, and I'm not even sure it's true?
NP is the class of decision problems where if the answer is YES and someone slips you a hint, you can solve them quickly (or quickly figure out that the hint was useless and report that). Where quickly means in polynomial time.
There's nothing about linear time in the classic definition.
pcstl 21 hours ago [-]
Sorry, you're correct. I meant "polynomial" rather than linear.
NP = nondeterministically polynomial. i.e. if you could evaluate all choices in parallel (or just "know" the right choice), then you'd get a polynomial runtime. That's what I was trying to informally hint at, but I ended up using the wrong term. I'll edit my original post.
That's equivalent to your description - the "hint" is knowing which of the options to choose.
The reason why superlinearity comes into play is that if you had a linearly growing amount of solutions to test then you'd just have a sum of polynomials, which is itself polynomial.
eru 21 hours ago [-]
Ok, I read your edited comment. Looks a lot better know.
One nitpick: I think your set of options needs to grow a lot faster than just superlinearly, I suspect it needs to grew superpolynomially?
However otherwise what you describe is essentially true of all problems in NP, not just the NP hard problems:
Sorting is (trivially) in NP, and you can say that to sort you need to pick one out of n! many permutations (which certainly grows superlinearly and even superpolynomially).
NP hard problems have the distinction that if you solve one of them efficiently, you can solve all of them efficiently, because you can reduce them to each other. (Basically because NP hard problems allow you to sort-of describe a computer, and reducing them to each other is equivalent to writing an interpreter or compiler.)
dnautics 21 hours ago [-]
the language around complexity domains is really confusing.
P means "this problem can be solved in polynomial # of steps relative to the problem size"
NP means "we don't know if the problem can be solved in polynomial # of steps relative to problem size, but we know we can check if the result is correct in a polynomial # of steps relative to the problem size"
!ETH: it was widely suspected that the flagship problem in NP, 3SAT, requires an exponential # of steps relative to problem size. We now know that 3SAT requires AT MOST something more than polynomial but strictly less than exponential to solve.
"P = NP" means "if you can check it in polynomial time, there's some way to solve it in polynomial time". "P != NP" means "there are some problems checkable in polynomial time for which there is no polynomial way to obtain the result"
Today's new proof makes "P = NP" "feel more likely", because we know that the flagship problem in NP is not exponential.
tfpgh 21 hours ago [-]
This isn't quite true, problems in NP can still require exponential time to solve.
Solving an arbitrary NP problem looks like first reducing that problem to SAT and then solving the equivalent SAT problem. We know (via the Cook–Levin theorem) that any NP problem can be reduced to SAT in polynomial time, and we now know that solving SAT is subexponential in terms of the size of the SAT problem, but it's possible for the conversion to SAT to grow the problem enough that it's exponential in terms of the original problem.
21 hours ago [-]
dnautics 20 hours ago [-]
thanks for the correction. Corrected.
jibalt 17 hours ago [-]
But even if every problem in NP is sub-exponential (which, as tfpgh notes, this result doesn't prove), how does that make it "more likely" that every such problem is solvable in a polynomial # of steps? I feel like it's a bit like claiming that, because Alex Honnold has shown that a human can free solo El Capitan in less than 4 hours, that makes it "more likely" that I could. To me, his success does not budge the latter probability at all.
It seems to me that the logic only goes the other way ... if ETH had been proven then it would follow that P != NP. With !ETH we really don't know any more about P ?= NP then we did before. Reasoning that P = NP is "more likely" strikes me as a form of a fallacy of affirming the consequent.
dnautics 3 hours ago [-]
that's why I wrote "feel more likely" in quotes. Emphasis on feel
caughtinthought 22 hours ago [-]
3SAT can't be solved in sub-exponential time
Fwiw never thought it was a well-named conjecture
pcstl 22 hours ago [-]
*Can be solved
This proves that EXP != NP
jibalt 19 hours ago [-]
This is not a proof that NP != EXP. NP is poly time reduceable to 3SAT + 3SAT is sub-exponential does not imply that NP is sub-exponential -- the cost of the reduction may be enough to push the conjunction from sub-exponential to exponential.
Whenever someone asks for an ELI5, there's always got to be somebody who further confuses the issue.
caughtinthought 21 hours ago [-]
Which is a separate issue than the one you commented originally
punty 5 hours ago [-]
If you look through Ryan Williams' x thread he links to a google drive folder (https://drive.google.com/drive/folders/1SAqEO1kt6wnA0NXuZecy...) with the OpenAI and Anthropic papers. There is also a new human contribution which is pretty accessible from Amit Sahai. I found this paper to be a more reasonable read, although the author(s) do state that their goal is to demonstrate a subexponential bound via an easier to follow approach.
Maybe it's a bit early to predict here but it feels like this approach might have a series of improvements similar to the progress made on the faster FFT multiplcation result.
js8 16 hours ago [-]
It would be interesting to see if this new counting method has any implications to counting 2SAT or parity-counting of 2SAT. Since problem posed in XORSAT and 2SAT clauses is NP-complete, this could have implications about P vs NP.
lisper 22 hours ago [-]
This seems huge, like not quite p=np but in the same league. Am I missing something ?
krackers 22 hours ago [-]
[deleted, originally wrote the hypothesis being true would imply NP=EXPTIME which is wrong, since there can be problems in EXPTIME which aren't in NP.
And the result that it's now false apparently doesn't imply NP!=EXPTIME either since it seems not strongly subexponential enough to offset the expansion in variables from reductions. See the other comments for a much better explanation.]
eru 21 hours ago [-]
> Instead we now know that NP is a strict subset of EXP (there are problems in NP that can be solved in subexponential time).
It's a bit more complicated than that, if you want to be careful. Sorting is in both NP and EXP and can be solved in subexponential time.
I think what they proved is that no problem in NP takes exponential time to solve. (Because you can always reduce them to SAT in polynomial time, and then solve SAT in subexponential time.)
EDIT: apparently the runtime bounds they gave here don't survive the usual polynomial reductions, thus they haven't proven that NP != EXP, it seems.
21 hours ago [-]
luc4 22 hours ago [-]
I mean the result that k-SAT cannot be solved in 2^{o(n)} clearly would imply P!=NP, but how does ETH imply NP = EXP? And how does \neg ETH imply NP != EXP?
22 hours ago [-]
lynndotpy 22 hours ago [-]
If I am understanding this correctly (and I am still reading this!) and if this is true, this means NP is sub-exponential. Sub-exponential does not mean P=NP. But yes, this is huge if true.
This means hard problems aren't as hard as we thought, and it's still possible P=NP. If it turns out to be true P=NP, we're a little closer to that. (I hope P!=NP!)
Every paper which assumes ETH is true might now have their conclusions be disproven.
cochne 22 hours ago [-]
It doesn't imply NP is sub-exponential, only that 3SAT is. Conversions to other problems can still end up exponential.
wbl 22 hours ago [-]
No. NP is always poly time reduceable to 3SAT
cochne 21 hours ago [-]
See this from the paper: "Note that runtime bounds of the form 2^o(n) do not transfer under general polynomial-time reductions (2^n^o(1) would be needed for this), so our result does not imply that general NP problems
admit subexponential time algorithms."
adgjlsfhk1 21 hours ago [-]
OTOH, it would be surprising if this sort of technique didn't apply to other NP problems.
jibalt 19 hours ago [-]
It's not clear what you're trying to say or the relevance. The fact remains that "NP is always poly time reduceable to 3SAT" and "3SAT is sub-exponential" does not imply that NP is sub-exponential.
adgjlsfhk1 17 hours ago [-]
right, but anything linearly reducable to kSAT is trivially sub-exponential, and a discovery like this means that linear reductions are a whole lot more important than they used to be.
Also for NP problems that can't linear reduce to kSAT just having the knowledge that SAT is sub-exponential (and the tools), makes it a lot more likely that we see a whole lot more problems become exponential.
calf 17 hours ago [-]
Yeah that would be interesting, like could there be different NP languages being sub-exponential but for entirely different reasons.
21 hours ago [-]
mswphd 21 hours ago [-]
practically, a poly-time reduction can increase teh size of hte problem instance. So maybe you transform a 3-color instance (graph on n vertices) into a n^2 sized SAT instance. You can then solve this in time 2^{n^2 / sqrt{log{n^2}}}, but this is not sub-exponential.
jibalt 19 hours ago [-]
Your "No" is wrong. As he said, "Conversions to other problems can still end up exponential", so (NP is poly time reduceable to 3SAT + 3SAT is sub-exponential) does not imply that NP is sub-exponential -- the cost of the reduction may be enough to push the conjunction from sub-exponential to exponential.
Did you reduce in the wrong direction or am I misunderstanding what you're trying to say?
lynndotpy 11 hours ago [-]
Yeah, I was wrong. Page two too, I commented too soon.
NP is not yet proven to be subexponential but still, ETH disproven is huge
22 hours ago [-]
jaggederest 22 hours ago [-]
This defeats a few hypotheses that were widely relied on.
strong exponential time hypothesis, and the titular exponential time hypothesis
It's not saying that these problems are easy, but it does demonstrate that they are much easier than previously believed. A decade ago if a human had published this kind of thing, and importantly if it held up, they would be almost certainly a strong candidate for some sort of award(s).
thatoneengineer 22 hours ago [-]
Assuming P != NP (and that this NP != EXP proof holds up), what's the next most "natural" candidate for how fast NP must grow? This paper appears to show Omega(2^(n/sqrt(log(n))) with a couple additional fudge factors which would be a very disappointing answer.
jibalt 19 hours ago [-]
This is not a proof that NP != EXP. NP is poly time reduceable to 3SAT + 3SAT is sub-exponential does not imply that NP is sub-exponential -- the cost of the reduction may be enough to push the conjunction from sub-exponential to exponential.
Even if all NP problems could be solved in sub-exponential time, it would not imply that NP ≠ EXP. It seems that many people here are confused about what EXP means – it’s the set of all problems that can be solved in at most exponential time, including those in P.
xigoi 12 hours ago [-]
This is not a proof of NP ≠ EXP. NP ≠ EXP would mean that there is a problem that can be solved in exponential time, but not in non-deterministic polynomial time. That’s completely different from what they have shown.
zeroonetwothree 21 hours ago [-]
Definitely puts some weight on the P=NP side of the scale!
SkiFire13 11 hours ago [-]
Not sure about how "natural" Omega(2^(n/sqrt(log(n))) is, but a huge intermediate result would be proving that QP = NP or QP != NP.
kakapo5672 22 hours ago [-]
My (very amateur) interpretation is that this weakens confidence in P!=NP. Would like to hear from some experts in this area, if this is so or not.
I’m not as smart as Scott but for me it’s more like 10% -> 20%. Do we have a prediction market for this?
jibalt 19 hours ago [-]
It seems highly irrational to bet that your evaluation is more likely than Aaronson's.
lostmsu 10 hours ago [-]
Not under the circumstances IMO
kibwen 19 hours ago [-]
Predictions markets are terrible mechanisms for this, because they require imposing an arbitrary time limit at which point the prediction will pay out. IOW, even if you religiously believed P=NP, but you think it would take at least two years to prove it, you would vote against the prediction if the deadline were one year.
internetter 19 hours ago [-]
Why must prediction markets have a predefined end date?
jibalt 19 hours ago [-]
Without it, capital would be trapped indefinitely.
howunfortunate 18 hours ago [-]
This is not necessarily true, you could have contracts rather than money down
throw-qqqqq 11 hours ago [-]
Sure, but in most (all?) financial settings, this would still count as exposure.
It doesn’t matter if I bet $N on something using cash or margin, my exposure is still $N.
Since you can’t have unlimited exposure, this would still lock up capital, until the bet can be resolved.
jibalt 17 hours ago [-]
[flagged]
FeepingCreature 12 hours ago [-]
Well, so? Then the prediction market would also price expected resolution time.
Tadpole9181 18 hours ago [-]
How would it work otherwise...?
internetter 16 hours ago [-]
Anybody can exit their contract by selling their contract to an interested party
hanyao_pan 7 hours ago [-]
[flagged]
21 hours ago [-]
pcstl 22 hours ago [-]
This proves that EXP != NP, which was a stronger claim than P != NP.
In a way it shows that NP is perhaps less distant from P than imagined. Whether it can be _reduced_ to P in some gigabrain way, or whether that can be shown to be impossible remains to be seen.
It is definitely progress towards an answer to P ?= NP.
jibalt 19 hours ago [-]
This is not a proof that NP != EXP. NP is poly time reduceable to 3SAT + 3SAT is sub-exponential does not imply that NP is sub-exponential -- the cost of the reduction may be enough to push the conjunction from sub-exponential to exponential.
There's a chain of classes P, NP(aka Sigma_1), Sigma_2, .., Sigma_n, ... PSPACE, EXPTIME. What we know for sure is that P < EXPTIME, others are unknown (well, maybe this paper adds something to this, time will tell).
It's conceivable that each of them is smaller than the next, but also that e.g. P < NP = all the sigmas < PSPACE < EXPTIME or many other possibilities. I think the general consensus is that it's more likely that there are more inequalities than not, but the fact is that we can't even show that P is less than PSPACE so far, which would be extraordinarily surprising if it were true.
caughtinthought 22 hours ago [-]
It basically just says that NP is not the same as EXP
jibalt 19 hours ago [-]
This is not a proof that NP != EXP. NP is poly time reduceable to 3SAT + 3SAT is sub-exponential does not imply that NP is sub-exponential -- the cost of the reduction may be enough to push the conjunction from sub-exponential to exponential.
Subexponential time still can mean much larger than polynomial time. There's a huge space between the two.
odyssey7 22 hours ago [-]
It’s not that it isn’t quite p=np; it actually isn’t p=np.
Still, an impressive accomplishment.
adgjlsfhk1 22 hours ago [-]
no. It's huge.
JonChesterfield 21 hours ago [-]
This construction splits the space into 'small' models with a quadratic lookup cost and 'large' with sub-exponential cost. The small one is by enumerating all SAT problems with their answers, then looking up the answer. The large one is something in polynomials I don't understand. An answer from openai about where the cutoff is was:
the constructed lookup machine has vastly more states than the estimated total number of physically distinguishable configurations of the observable universe.
I'm not inclined to consider "wrote down all the answers ahead of time, so that's free" as a quadratic time solution to SAT. Nor very convinced by the other half.
So on balance, if this is considered proof that the exponential time hypothesis is false, and openai model reading of the lean was vaguely on point, then I reject the axioms of this system. Not a proof, even if there is lean. I'm OK with being downvoted for that position.
hansvm 18 hours ago [-]
Double-checking, is this more like the recent DFT improvement where even the word-RAM model of computation doesn't justify the fraction of a log factor they eliminated because of an assumption of arbitrary-precision arithmetic, or has ETH actually fallen with the Lean proof being formulated appropriately? Do we know yet?
adgjlsfhk1 17 hours ago [-]
The DFT result isn't RAM specific. It holds up in multi-tape turing machines. (it is, however, galactic).
hansvm 16 hours ago [-]
That doesn't sound right. Previous results proved that with bounded values you couldn't beat O(nlogn), among other things. The OpenAI result explicitly used arbitrary-precision complex arithmetic. Yes, it's galactic [0], but either it's wrong or the previous results were wrong, no?
[0] Very much not something I care much about in these sorts of conversations. Even if it weren't galactic, a random logn factor here and there usually loses to cache efficiency and whatnot. Their speedups were less than that, and I'd already assumed we were in the realm of applied math rather than real engineering.
adgjlsfhk1 15 hours ago [-]
> but either it's wrong or the previous results were wrong, no?
Not quite. This result uses polylog(n) precision which isn't bounded, so it escapes the previous bounds. This doesn't noticably affect the runtime because not all of the math needs this extra precision (in this case you need a couple computations in higher precision but less than n operations), so the extra precision can be payed for even in a TM/circuit model.
lg5689 15 hours ago [-]
Are you thinking of the int multiplication result instead? The DFT result uses a computation model with unlimited precision reals.
adgjlsfhk1 15 hours ago [-]
no. The DFT result as published uses unlimited precision, but the comparison with the int multiplication shows that the unlimited precision just makes the paper shorter/easier rather than being an exploit in the computation model.
choeger 13 hours ago [-]
I am long out of this game, but the complexity class they show still has an n in the exponent, even if divided by log(n).
I have no intuition whatsoever on how that algorithm scales. Can anyone enlighten me?
SkiFire13 11 hours ago [-]
The algorithm is still exponential, it just not in the class that the ETH claims. In practice it's likely worse than current algorithms for any reasonable input you might throw at it, and starts getting faster only once the problem is already too big.
punty 6 hours ago [-]
2^(n/logn) will eventually be smaller than (1+epsilon)^n for any fixed positive epsilon. However, as log(n) grows quite slowly n will have to be exceptionally large. For epsilon=2^-D n will have to be something like 2^(2^D) large.
13 hours ago [-]
rnbnnnn 17 hours ago [-]
Higgledy-piggledy,
Exp. Time Hypothesis:
Runtime complexity
Soars to the sky.
Subexponentially,
Tensor contractions have
Tallied solutions for
OpenAI.
It is remarkable -- and, when you think about truly astronomical sized problems, kind of unsettling that when you're searching for SAT you only have to check an arbitrarily small percent of the solution space
marshray 21 hours ago [-]
If I can "count the satisfying assignments of a k-CNF in subexponential time and polynomial space", could I just count the the solutions for assignments of 0 and 1 to x_1, then proceed with whichever is greater (or nonzero), counting the solutions for x_2=0, and so on.
Doesn't that lead me to an existence proof (i.e., a solution) to a k-SAT problem in N*(subexponential_time and polynomial_space)?
And with constant folding, N is reduced by 1 on each iteration.
What obvious thing am I missing here?
moktonar 8 hours ago [-]
I bet if we live in a simulation then P == BQP, and viceversa. I’d love to throw this at those models..
airtnp 16 hours ago [-]
I still think P != NP, I would assume 2^{n/log(n)} is an elegant optimal boundary.
bozdemir 14 hours ago [-]
No practical implications, we dont use 10^87 variables (a point where the proposed new method surpasses the already existing sat solvers), however a good theoritical point.
nemo44x 21 hours ago [-]
We are living in such a weird, amazing, and miraculous time. It’s completely surreal.
cubefox 15 hours ago [-]
> Given this news, I’ll up my personal probability of P=NP from 3% to 5%.
— Scott Aaronson
antics 21 hours ago [-]
Perhaps this will be the push we need to finally, seriously consider the possibility that our formalisms of “efficient” and “efficiently verifiable” algorithms correspond to nothing resembling reality, and P \in NP is actually ill-posed.
This has been marginally debated since the mid 90s, when Impagliazzo published the “5 worlds” survey. Occasionally it is brought up in talks about average case analysis. There is occasionally a workshop about it. But it has never really got the attention it deserved. How many more of these results do we need to take it seriously? (Assuming we do indeed certify it.)
eru 21 hours ago [-]
> Perhaps this will be the push we need to finally, seriously consider the possibility that our formalisms of “efficient” and “efficiently verifiable” algorithms correspond to nothing resembling reality,
What do you mean? Do you mean that our heuristics shortcuts of treating P as efficiently solvable (and NP as efficiently verifiable) are not warranted? So far pretty much all algorithms in P that we found have small exponents. That hasn't changed, but it might change in the future.
Or do you mean something else?
Keep in mind that even most instances of many NP hard problems can be solved very efficiently in practice, because most instances ain't hard.
However we know problems that are expected to be 'easier' than NP that are hard to solve in practice. These are pretty much all the problems we build cryptography out of, because essentially these problems are in the intersection of NP and co-NP and that's expected to be smaller than NP. And cryptography has to be hard to break on average to work: a random key needs to be a good key.
> and P \in NP is actually ill-posed.
Oh, that's very simple to answer: P is not an element of NP. The question people care about is whether there's any element in NP that's not in P. In LaTeX notation P \subset NP vs P \subseteq NP.
I'm not sure what you mean by ill-posed? The question is very clear. What are you trying to say?
antics 20 hours ago [-]
"Ill-posed" here means that the formalisms we've chosen to represent "efficient" and "efficiently verifiable" algorithms could turn out to not correspond to anything humans would consider meaningful ("we posed the problem poorly"). For most people, a solution to an NP-complete problem that's barely-subexponential would be clear evidence of these formalisms being ill-posed.
There are many ways it might turn out to be ill-posed, this is just one of them. Impagliazzo's "5 worlds" survey is in some sense a catalog of some of these ways, and includes some of the ways you seem to be referencing (approxmations, probabilistic techniques, average-case efficiency; depending what you mean this could lie in the "Heuristica" world).
eru 20 hours ago [-]
> "Ill-posed" here means that the formalisms we've chosen to represent "efficient" and "efficiently verifiable" algorithms could turn out to not correspond to anything humans would consider meaningful ("we posed the problem poorly").
OK, that's a reasonable worry and one that practitioners share. Thanks for explaining. Though I don't think ill-posed is a good term for this, the technical meaning of the term points in a different direction.
So far, as far as I can tell this new result gives much of any extra credence to that worry.
antics 19 hours ago [-]
It is completely acceptable in math to use "ill-posed" to indicate that something is insufficiently specified, improperly formulated, or ambiguous. Math people do this all the time.
eru 7 hours ago [-]
And that's fine. But here the question is perfectly well specified and properly formulated and not ambiguous at all.
The problem is that this formal question might not correspond to the informal question we actually care about.
antics 5 hours ago [-]
You can hold that position if you like but you should do so knowing that the vast majority of people (including math people) would say that a formalism that classifies a technically-subexponential solution to an NP-complete problem as “efficient” is in fact improperly formulated, because the goal was specifically to formalize our intuition of efficiency. Our formulation in that case would have failed to do the single thing we laid out for it. Textbook improper formulation. There is not another way of putting this.
calf 2 hours ago [-]
The technical result has nothing to do with "efficient" which according to textbook CS theory roughly defines it to be the set P, the strictly polynomial time algorithms. Has nothing to do with the ETH result which is still an exponential, 2^(n/ log n), just not a pure exponential.
I'm also confused what you are saying down here. Though I can see how "sub-exponential" is easily misleading terminology.
reenorap 17 hours ago [-]
What about OpenAI allowed ETH to be determined to be false that couldn't be done by humans? Was there something in particular that OpenAI's AI did that help bridge the gap to a solution?
hardbass 13 hours ago [-]
What about a particular mathematician solving a problem that couldn't be solved by other mathematicians?
martin-t 11 hours ago [-]
I wonder if LLMs are good at math because there's very little math at this level that is wrong.
With code, there's always plenty of bugs, hacks, quick "temporary" solutions, etc. But in math, a proof either exists or it doesn't and they can always be automatically verified using tools like Lean.
silentmafia 10 hours ago [-]
where be the appendices?
deadbabe 12 hours ago [-]
I’m shaking, so much has happened in the past few years, I think it’s inevitable we will find the efficient algorithm for P=NP. Not sure if I’m ready to live in that world yet.
gf000 5 hours ago [-]
From another comment:
> 10^87 variables, a point where the proposed new method surpasses the already existing sat solvers
Yeah, it's not efficient in the ordinary sense.
colordrops 14 hours ago [-]
I remember the olden days when LLMs couldn't count.
dgellow 12 hours ago [-]
Funnily enough it is still the case! Still not possible to get an LLM to count from 1 to like 500 without stoping or making a mistake. Unless of course you delegate that to writing a script or other external tooling
thescobey 12 hours ago [-]
not true. Unauthenticated chatgpt just did that for me up to 2000 with no mistakes
dachtovyvse 10 hours ago [-]
I don:t think these are exactly llms what you are seeing here..
sevenzero 14 hours ago [-]
Any implications on what could be achieved with this information, for a non academic?
Kina 14 hours ago [-]
There is nothing immediately useful or practical from this.
TZubiri 19 hours ago [-]
I'm not the kind of programmer that even understands P=NP, so I'll either be way off base, or be blessed with an outsider perspective.
Considering that no human will be able to sift through these in no less than a team-decade, to verify that there's no mistake, yet still that will be massively less compute than the one necessary to produce the 'solution', isn't the empirical finding contrary to the theoretical finding being suggested? Namely that in practice we are generating these 'proofs' in a massive amount of compute time, but it will take tiny amounts of time to verify them.
Is it very useful to talk about computing in purely mathematical terms and not in empirical terms? There's very obvious truths that we are seeing here, and it seems like those that go through some sort of rigorous mathematical training kind of fail to see it. Similar to how 70% of physicians or something believe in the Many Worlds Interpretation or that time isn't real, a sort of algebraic psychosis where one is removed from a human reality that we have access to in order to attempt getting close to an 'objective reality' that is far removed from the human experience.
To some extent we are computing entities, so I don't even think that we can conceive of computing as decoupled from ourselves[1]. I know the observer effect is very often mis-cited by laymen, but I'll be damned if some computer scientists like Godel don't sound like they were up to something similar to this.
Also, here's another outsider perspective. This is obviously slop, I'm not sure how but it's obviously nerd-sniping the CS majors that understand this, because it's obviously very hard to find the flaw, but it gives epicycles energy. It's also sufficiently complex that under a bayesian analysis it is more likely that the AI has reached the limit of its processing power until it becomes confused enough to believe it has reached something significant, kind of like how I'm doing now.
[1] xkcd://1163
mattm 17 hours ago [-]
> Considering that no human will be able to sift through these in no less than a team-decade
How do you figure that? For ETH, OpenAI is engaging with top experts in this area. It's unlikely that they'll need 10 man-years combined to go through the results:
> This work will be verified and shepherded by a group led by Russell Impagliazzo (UC San Diego), Ramamohan Paturi (UC San Diego), and Ryan Williams (MIT). All three are experts in algorithm design and complexity theory.
> Impagliazzo and Paturi, along with Francis Zane, are the original proposers of the Exponential Time Hypothesis, and have authored a number of influential papers on the topic over the last 30 years.
> Williams has refuted strong versions of the ETH, used ETH for hardness results, and connected algorithms and lower bounds.
TZubiri 16 hours ago [-]
I think I misread something, the pdf is like 80 pages long, and there’s a list of like 200 pdfs, each around that length, I thought they were all related to this proof, but they are unrelated.
jaekwon 21 hours ago [-]
[flagged]
zahlman 13 hours ago [-]
Humans in this thread have already explained that concept with much more straightforward prose.
From the HN comment guidelines:
> Don't post generated text or AI-edited text. HN is for conversation between humans.
Disclosure doesn't address the objection (not that it wouldn't be obvious anyway). If you learned something from an AI convo, tell us what you learned, in your own words, not what the LLM said.
baggy_trough 22 hours ago [-]
[flagged]
freecodeio 22 hours ago [-]
math major here, I can't read the paper for shit
moishe_syzslak 20 hours ago [-]
Not a math major here. But is this paper way too long? So long that it raises the possibility that OpenAI's staff mathematicians passed through AI's raw output as-is?
eru 21 hours ago [-]
That problem seems independent of the 'stochastic parrot' accusation?
freecodeio 21 hours ago [-]
A parrot might squeak the theory of everything and it won't matter to any of us cause nobody speaks parrot.
eru 21 hours ago [-]
We can record a lot of parrot speech and train LLMs against it and eventually build a translator.
They are making good progress on similar research programmes for many cetaceans.
In the case of our stochastic parrots it's even easier, since they already speak something like human language. And for the math proofs it's even easier, because once they are formalised into something like Lean the humans only need to understand the statement of the theorem, and a mechanical computer program can check the proof.
freecodeio 21 hours ago [-]
Yes we can just train llms against it and it's all solved. Just a few more trillion dollars and a bunch of deforestation for datacenters bro.
CaptWorld 16 hours ago [-]
Ironically yeah.. if it can solve more complex problems across domains like biology, econ, finance then all the deforestation is worth it
freecodeio 10 hours ago [-]
I would take a living, breathing forest over math papers that nobody knows what to do with. Hell I would take a leaf with an ant over it.
aaron695 21 hours ago [-]
[dead]
elzbardico 21 hours ago [-]
It is just that we never considered how advanced stochastic parrots could be so powerful when dealing with basically the whole library of acquired human knowledge and guided by experts to generate.
It is not a demerit, actually I think that it is a very elegant outcome how many problems could be solved by generation and this probably show us how language is a far more important thing than we ever thought it was.
kevinwang 19 hours ago [-]
wtf......
whattheheckheck 22 hours ago [-]
Is this really as interpetable math is fundamentally. Like wtf is this accessibility? who is this for? Do top mathematicians read this like a chapter book? Absolutely ridiculous they have all this compute and creative resources and cant make something more intuitive to help people understand it more natively
vecter 21 hours ago [-]
It's a math paper written for mathematicians.
It's not possible for someone who's not a specialist in the field to understand it (unless there are more elementary proofs, of which likely none exist).
eru 21 hours ago [-]
Even mathematicians take a long time to read math books and articles, especially if they go into the details. They don't read math like you would read a novel.
xeonmc 19 hours ago [-]
> They don't read math like you would read a novel.
siting on a recliner making an occasional sensible chuckle while flipping through the pages?
NetMageSCW 21 hours ago [-]
Sometimes hard things are hard.
atlex2 21 hours ago [-]
Actually, no - this is what controllability is all about. Humans have to understand it.
elzbardico 21 hours ago [-]
Humans can understand it. Not all of them, because to understanding it, there's a lot of other things you need to understand before.
paxy 19 hours ago [-]
It's sometimes okay to look at something, go "this isn't for me", and move on. You don't need to have an opinion on everything.
whattheheckheck 15 hours ago [-]
Same to you bud
ks2048 18 hours ago [-]
> Absolutely ridiculous they have all this compute and creative resources and cant make something more intuitive to help people understand it more natively
OpenAI has that too - open their website and ask.
whattheheckheck 15 hours ago [-]
And get some hallucinated slop infotainment?
serf 19 hours ago [-]
I agree with you insofar that the primary motivator for these press releases is public relations and investor confidence, so it should be made as minimally hard to understand as possible just by sheer virtue that it exposes oAI to more cash thrown at them.
I totally disagree with you on the precept that all difficult to understand things need be needlessly dumbed-down/watered-down until palatable for a mass (average) audience. Requiring 'math50' before 'trig101' isn't gate-keeping in any moral sense, it's an effort to save everyones' time involved when the effort is futile.
Similarly I don't demand that haute couture fashion companies explain the style to me until 'I get it' ; I just take it for granted that i'm not going to be able to understand the entirety of the world in one lifetime.
eru 9 hours ago [-]
> I agree with you insofar that the primary motivator for these press releases is public relations and investor confidence, so it should be made as minimally hard to understand as possible just by sheer virtue that it exposes oAI to more cash thrown at them.
Why? The investors can just ask Claude or Gemini whether the proof holds up.
- Early CS researchers like Donald Knuth entered CS in the days when regularly someone would come up with a surprising faster algorithm for some problem, and their intuitions were that most problems had faster algorithms than you'd expect.
- Later generations of CS researchers, as all the easy algorithms were discovered, and post Karp's definition of NP-completeness (and the Garey & Johnson book, say), began to specialize in proving hardness, and complexity theory with a “zoo” of complexity classes became more about separation and lower bounds, e.g. I've seen algorithms like Arora's PTAS for Euclidean TSP being described as a “failed attempt to prove a lower bound”. So an entire generation of researchers' intuition was mostly in the direction of an elegant universe with neat separation results (even if we couldn't get them).
- So e.g. surveys of computer scientists showed most of them believing that P≠NP, and someone like Knuth has always seemed a bit of an outlier for saying that maybe P=NP: his argument was simply that there are so many possible polynomial-time algorithms that we haven't explored, and maybe one of them with a large exponent could solve NP-complete problems. (In response to arguments that many researchers have failed to find any such algorithms, he would say that many researchers have failed to prove that P≠NP.) E.g. in 2017 when Scott Aaronson wrote his survey (https://www.scottaaronson.com/papers/pnp.pdf = https://www.scottaaronson.com/papers/pnp-kindle.pdf) he wrote:
> Admittedly, it can be hard to tell whether declarations that P = NP are meant seriously, or are merely attempts to be contrarian. However, we can surely agree with Knuth and Lipton that we’re far from understanding the limits of efficient computation, and that there are further surprises in store.
- What we've seen in this month is surprising unexpected algorithms, like o(n log n) algorithms for FFT and integer multiplication, and now this sub–exponential-time algorithm for 3-SAT. (Yes the ETH has had less support than P≠NP but I still gather it's unexpected.)
So (though I don't expect intuitions on P≠NP to change, and probably that's still the right intuition… but I'm just an interested amateur), maybe there will be a bit of a swing of the pendulum back to the idea that maybe clever algorithms exist that we just haven't thought of.
In cryptography, most of the problems believed to be exponentially hard, such as factoring, don't have proofs of an exponential lower bound. There's some risk of a breakthrough that makes those problems easier. A probabilistic solution would be good enough to break many cryptosystems.
I suspect that people at the cryptanalysis agencies worldwide are staying up late tonight, trying to figure out the impacts and risks of this new result.
These are by far not most, nor most of the practically useful ones. Directed graph reachability, given an adjacency list as input, is NL-hard.
> In fact, one of the first things I wanted OpenAI to check is that no existing cryptosystems are compromised by the result. Apparently they are safe...
so if you trust his trust of OpenAI, then this has no (immediately obvious) bearing on cryptosystems for now.
It also not probabilistic, so linear programing is not rely a good example
It is notable that simplex, especially dual simplex is often better in practice, especially for integer linear programming with branch and bound because you only have to slightly modify the parent optimal basis in simplex vs entirely restarting or refactorizing for interior point methods.
There are subexponential algorithms for integer factorization, e.g., the general number field sieve and Lenstra’s ECM.
Actually, integer factorization already has subexponential-time algorithms, such as the General Number Field Sieve (GNFS).
The fact that other math problems are bulk solved yet nothing from cryptography was released/published as solved could be a strong indicator that "all modern public key based cryptography" could have been at risk.
“Could be”, but I think the correct way to describe it is “the general public doesn’t know”. It could be any of
- they tried very hard without finding weak spots
- they tried for a while, and gave up because the LLMs didn’t even produce leads
- they tried, found something and kept it for themselves
I think the first is not unlikely. Before LLMs, the likes of the NSA must have looked really hard into these problems, and IMO it’s not likely they found something substantial (if they did, their counterpoints in other large countries likely would find it, too, and some of them would have used that knowledge)
Here's a nice low-budget scifi movie about this:
https://en.wikipedia.org/wiki/Travelling_Salesman_(2012_film...
https://www.youtube.com/watch?v=OgeyHkP6i3g (full movie)
https://www.goodreads.com/book/show/37986693-factor-man
I mean if someone develops an O(n^100) algorithm for solving an NP-complete problem, that would prove P=NP, but pose no immediate threat to cryptography.
It increases risk, in that a galactic algorithm increases the odds that an efficient algorithm exists waiting to be found, but it is entirely (epistemically) possible that the galactic algorithm exists but the efficient algorithm doesn't.
https://www.informit.com/articles/article.aspx?p=2213858&WT....
> Don Knuth: As you say, I've come to believe that P = N P, namely that there does exist an integer M and an algorithm that will solve every n-bit problem belonging to the class N P in n**M elementary steps.
> In 2019, Harvey and van der Hoeven came up with a galactic algorithm with complexity O ( n log n ) {\displaystyle O(n\log n)}. This matches a guess by Schönhage and Strassen that this would be the optimal bound.
> In September 2026, OpenAI released a preprint claiming an algorithm with complexity O ( n ( log n ) α ) {\displaystyle O(n(\log n)^{\alpha })} with α < 1 {\displaystyle \alpha <1}
https://en.wikipedia.org/wiki/Multiplication_algorithm
That said, it's interesting to contemplate that there is "space between" polynomial and exponential time complexities.
Yes, svat’s comment accounts for that by using little-o notation* in o(n log n). This was only achieved in the 2026 result.
* https://en.wikipedia.org/wiki/Little_o_notation
Edit: To explain more, it is guaranteed that you can reduce any NP problem to 3SAT in polynomial time with a polynomial factor in input size. You still have to solve it.
If 3SAT were solvable in polynomial time, then polynomial(polynomial(x)) = polynomial(x) and you're implied to have an overall polynomial time solution.
But what we have here is that 3SAT is solveable in subexponential time. subexponential(polynomial(x)) is not guaranteed to be sub-exponential.
Further edit: The subexponential solution does carry over to any (?) problems that have can be reduced to 3SAT in a linear number of variables. They list: Counting independent sets, Counting proper q-colorings, Counting perfect matchings.
Wouldn't that also include functions that can be evaluated in hardware using a fixed number of gates? E.g., symmetric cryptography?
Is there a subset of NP problems for which a subexponential algorithm would witness the entire NP class being subexponential?
EDIT: DISREGARD THAT I WAS MISTAKEN
If subexponential just means 2^{o(n)}, (as it is here, O(2^{n/\sqrt{\log n}})), then no. E.g. if the cost of the reduction took you from n to \sqrt{\log n}n, then you'd be back to exponential time. The Subexponential Reduction Family is the class of problems that preserve subexponential time in the second sense.
Put these two together and you would think that they would mean that any NP complete problem can be solved in sub-exponential time. But this isn't necessarily true because changing the NP complete problem into 3SAT can increase the number of variables, which can theoretically negate the sub-exponential time.
(By the way, I think you mean NP-complete, not NP-hard. The Halting Problem is NP-hard.)
So the reduction to 3SAT could happen in principle, but it isn’t a necessary step.
P=/=NP -> 3SAT has no polynomial-time algorithm
ETH is true -> 3SAT has no subexponential time algorithm
ETH is false -> 3SAT has a subexponential time algorithm
------
ETH true -> P=/=NP
ETH false (!!!) -> P ?= NP remain unsolved
but
2^(sqrt(n)^2) = 2^n
This also means your other comment here is wrong to suggest any error: https://news.ycombinator.com/item?id=50254142
So 3SAT+poly reduction ends up being exponential
In this case they have c = 1-0.5(\log \log n)/(\log n) which is approaching 1 for large n.
It's still a big result, but it's mostly theoretical. It might help explain, structurally, why most SAT instances are far easier than an exponential model would indicate.
then 2^(n^(1-epsilon)) belongs to 2^o(n)
Suppose p(n) is some polyonomial in n, our polynomial reduction. Let's make it a monomial for simplicity, p(n) = n^a
Does 2^(p(n)^(1-epsilon)) necessary belong to 2^o(n)?
No, that only holds if (n^a)^(1-epsilon) = n^(a (1-epsilon) ) < n^1 . So, it fails for p(n) = n^a for any a such that a >= 1/(1-epsilon)
No, subexponential is not the same as polynomial time. There's sub-exponential functions that grow faster than polynomial.
> Somehow, their wide range of results touch every single area of math except anything touching cryptography. I think it's fair to expect that three letter agencies are given the ability to veto the publication of certain discoveries.
https://news.ycombinator.com/item?id=50256998
The big AI companies spend millions on some of these proofs (15M was one estimate for the Naiver-Stokes thing). Had anyone has spent millions on them before this? There was a 1M prize but that certainly wouldn't convince anyone to spend orders of magnitude more to solve the problem.
Meanwhile the three letter agencies are spending billions on cryptography. They have programs that recruit students starting in high school. So maybe they are sending the spooks to suppress OpenAI's cryptography breakthroughs, or maybe they just already outspent them.
That to me is the point that isn't getting enough attention: pure math isn't that well funded. I agree as much as anyone that these proofs are an unprecedented breakthrough for LLMs, but let's keep in mind that the money they are throwing around is also unprecedented.
It’s possible they have major findings in crypto but are coordinating disclosure. The PHP bug was worked for months and only leaked a few hours early.
It’s also possible they have not found any major flaws yet. The math underlying major cryptography libraries is way simpler than these advanced proofs, and the implementations among the most scrutinized and hardened bits of code in the world.
The PHP bug paradoxically gave me hope. It was not magic; it was a logic flaw that was already known for years. And exploiting it has proved way more difficult than initially feared.
I think the premise does support the conclusion that there's some mechanism suppressing release, though.
If I were to start inferring what’s going on, it’s that findings in this space have relevance to breaking current weak cryptography.
Can an expert in sat solving comment if there's any immediate applications of the method from the paper? Or is SAT solving in general pretty far away from worst-case times, and this is a theoretical algorithm which would be hard to apply in practice.
** Yes, I know that's proven to be impossible.
If objects have a maximum size of 4 GB (= 2^35 bits), then arbitrary objects can be sorted in O(n) using 2^2^35 bits of memory.
[1] https://en.wikipedia.org/wiki/Bucket_sort
Yes, I think we can pretty safely say that the algorithm in the paper is not used due to practical constraints. This is a subjective judgment, but pretty clear from the paper that the algorithms aren't practical to apply.
> We prove that the time complexity of self-attention is necessarily quadratic in the input length, unless the Strong Exponential Time Hypothesis (SETH) is false[...]
If OpenAI's proof is correct, does that mean self-attention can be implemented in sub-quadratic time? I.e. we could eventually have all the most advanced LLMs running on cheap hardware? To put it more playfully, is ETH being false actually bearish for Nvidia?
[1]: https://arxiv.org/abs/2209.04881
What is relevant is that the logic goes the other way: SETH implies quadratic, !SETH implies nothing.
But it's also not even wrong, in the Pauli sense.
That makes me wonder if "I see your CS proof, how does this affect LLMs / nvidia stonk price???" being immediately self-described as "playful" ensures criticism looks cranky.
Turns out, it affected the global politics tremendously.
https://news.ycombinator.com/item?id=50255159
I'm reminded of the Apollo program that was cool for a while, but eventually the public lost interest.
Maybe it becomes cheaper? Maybe other labs want to prove their worth will pick up the slack when another loses interest?
sure, this proof itself doesn't settle the P/NP problem, but we've lost one of our core beliefs.
A common complexity theory misunderstanding is that statements like this applies to all or even most instances-- and it leads to objectively bad engineering of the form "oh look this is actually 3sat, it's unsolvable".
(Great fodder for a midwit meme: idiot and genius say "my heuristics go brrr!"-- midwit says "No no no! NP problems can't be efficiently solved!")
Any specific instance may be efficiently solvable (and perhaps all instances coming from your particular problem set -- a subset of all possible 3sats).
So I would add to that paragraph "at least for some 3sat instances".
The Exponential Time Hypothesis in effect says that 3SAT can only be solved by brute force--trying every possible combination until you find the right one. If your 3SAT expression has 100 variables, then this will take about 2^100 tries (exponential time).
What they found was an algorithm faster than brute force. 3SAT is still potentially one of these hard problems, but finding anything faster than brute force is a major advance.
NP-complete problems are essentially those where you need to make some kind of choice over a superlinearly-growing set of options where each option can be solved in polynomial time. Like, for example, finding a route between cities on a map under a certain total distance. You might need to go over all choices of routes.
The ETH essentially assumes that the best solution (in terms of complexity, i.e. how it grows) you can get for these kinds of problems is exponential. OpenAI just proved that this is false, you can have solutions that are below exponential complexity (but still above polynomial - if anyone finds a polynomial solution then we'd have proven that P=NP)
Seems like a weird way to describe NP, and I'm not even sure it's true?
NP is the class of decision problems where if the answer is YES and someone slips you a hint, you can solve them quickly (or quickly figure out that the hint was useless and report that). Where quickly means in polynomial time.
There's nothing about linear time in the classic definition.
NP = nondeterministically polynomial. i.e. if you could evaluate all choices in parallel (or just "know" the right choice), then you'd get a polynomial runtime. That's what I was trying to informally hint at, but I ended up using the wrong term. I'll edit my original post.
That's equivalent to your description - the "hint" is knowing which of the options to choose.
The reason why superlinearity comes into play is that if you had a linearly growing amount of solutions to test then you'd just have a sum of polynomials, which is itself polynomial.
One nitpick: I think your set of options needs to grow a lot faster than just superlinearly, I suspect it needs to grew superpolynomially?
However otherwise what you describe is essentially true of all problems in NP, not just the NP hard problems:
Sorting is (trivially) in NP, and you can say that to sort you need to pick one out of n! many permutations (which certainly grows superlinearly and even superpolynomially).
NP hard problems have the distinction that if you solve one of them efficiently, you can solve all of them efficiently, because you can reduce them to each other. (Basically because NP hard problems allow you to sort-of describe a computer, and reducing them to each other is equivalent to writing an interpreter or compiler.)
P means "this problem can be solved in polynomial # of steps relative to the problem size"
NP means "we don't know if the problem can be solved in polynomial # of steps relative to problem size, but we know we can check if the result is correct in a polynomial # of steps relative to the problem size"
!ETH: it was widely suspected that the flagship problem in NP, 3SAT, requires an exponential # of steps relative to problem size. We now know that 3SAT requires AT MOST something more than polynomial but strictly less than exponential to solve.
"P = NP" means "if you can check it in polynomial time, there's some way to solve it in polynomial time". "P != NP" means "there are some problems checkable in polynomial time for which there is no polynomial way to obtain the result"
Today's new proof makes "P = NP" "feel more likely", because we know that the flagship problem in NP is not exponential.
Solving an arbitrary NP problem looks like first reducing that problem to SAT and then solving the equivalent SAT problem. We know (via the Cook–Levin theorem) that any NP problem can be reduced to SAT in polynomial time, and we now know that solving SAT is subexponential in terms of the size of the SAT problem, but it's possible for the conversion to SAT to grow the problem enough that it's exponential in terms of the original problem.
It seems to me that the logic only goes the other way ... if ETH had been proven then it would follow that P != NP. With !ETH we really don't know any more about P ?= NP then we did before. Reasoning that P = NP is "more likely" strikes me as a form of a fallacy of affirming the consequent.
Fwiw never thought it was a well-named conjecture
This proves that EXP != NP
Note https://news.ycombinator.com/item?id=50253213 which explains it better.
Note https://news.ycombinator.com/item?id=50253213
Maybe it's a bit early to predict here but it feels like this approach might have a series of improvements similar to the progress made on the faster FFT multiplcation result.
And the result that it's now false apparently doesn't imply NP!=EXPTIME either since it seems not strongly subexponential enough to offset the expansion in variables from reductions. See the other comments for a much better explanation.]
It's a bit more complicated than that, if you want to be careful. Sorting is in both NP and EXP and can be solved in subexponential time.
I think what they proved is that no problem in NP takes exponential time to solve. (Because you can always reduce them to SAT in polynomial time, and then solve SAT in subexponential time.)
EDIT: apparently the runtime bounds they gave here don't survive the usual polynomial reductions, thus they haven't proven that NP != EXP, it seems.
This means hard problems aren't as hard as we thought, and it's still possible P=NP. If it turns out to be true P=NP, we're a little closer to that. (I hope P!=NP!)
Every paper which assumes ETH is true might now have their conclusions be disproven.
Also for NP problems that can't linear reduce to kSAT just having the knowledge that SAT is sub-exponential (and the tools), makes it a lot more likely that we see a whole lot more problems become exponential.
Note https://news.ycombinator.com/item?id=50253213 which explains it better.
NP is not yet proven to be subexponential but still, ETH disproven is huge
strong exponential time hypothesis, and the titular exponential time hypothesis
It's not saying that these problems are easy, but it does demonstrate that they are much easier than previously believed. A decade ago if a human had published this kind of thing, and importantly if it held up, they would be almost certainly a strong candidate for some sort of award(s).
Note https://news.ycombinator.com/item?id=50253213 which explains it better.
It doesn’t matter if I bet $N on something using cash or margin, my exposure is still $N.
Since you can’t have unlimited exposure, this would still lock up capital, until the bet can be resolved.
In a way it shows that NP is perhaps less distant from P than imagined. Whether it can be _reduced_ to P in some gigabrain way, or whether that can be shown to be impossible remains to be seen.
It is definitely progress towards an answer to P ?= NP.
Note https://news.ycombinator.com/item?id=50253213 which explains it better.
It's conceivable that each of them is smaller than the next, but also that e.g. P < NP = all the sigmas < PSPACE < EXPTIME or many other possibilities. I think the general consensus is that it's more likely that there are more inequalities than not, but the fact is that we can't even show that P is less than PSPACE so far, which would be extraordinarily surprising if it were true.
Note https://news.ycombinator.com/item?id=50253213 which explains it better.
Still, an impressive accomplishment.
So on balance, if this is considered proof that the exponential time hypothesis is false, and openai model reading of the lean was vaguely on point, then I reject the axioms of this system. Not a proof, even if there is lean. I'm OK with being downvoted for that position.
[0] Very much not something I care much about in these sorts of conversations. Even if it weren't galactic, a random logn factor here and there usually loses to cache efficiency and whatnot. Their speedups were less than that, and I'd already assumed we were in the realm of applied math rather than real engineering.
Not quite. This result uses polylog(n) precision which isn't bounded, so it escapes the previous bounds. This doesn't noticably affect the runtime because not all of the math needs this extra precision (in this case you need a couple computations in higher precision but less than n operations), so the extra precision can be payed for even in a TM/circuit model.
I have no intuition whatsoever on how that algorithm scales. Can anyone enlighten me?
Doesn't that lead me to an existence proof (i.e., a solution) to a k-SAT problem in N*(subexponential_time and polynomial_space)?
And with constant folding, N is reduced by 1 on each iteration.
What obvious thing am I missing here?
— Scott Aaronson
This has been marginally debated since the mid 90s, when Impagliazzo published the “5 worlds” survey. Occasionally it is brought up in talks about average case analysis. There is occasionally a workshop about it. But it has never really got the attention it deserved. How many more of these results do we need to take it seriously? (Assuming we do indeed certify it.)
What do you mean? Do you mean that our heuristics shortcuts of treating P as efficiently solvable (and NP as efficiently verifiable) are not warranted? So far pretty much all algorithms in P that we found have small exponents. That hasn't changed, but it might change in the future.
Or do you mean something else?
Keep in mind that even most instances of many NP hard problems can be solved very efficiently in practice, because most instances ain't hard.
However we know problems that are expected to be 'easier' than NP that are hard to solve in practice. These are pretty much all the problems we build cryptography out of, because essentially these problems are in the intersection of NP and co-NP and that's expected to be smaller than NP. And cryptography has to be hard to break on average to work: a random key needs to be a good key.
> and P \in NP is actually ill-posed.
Oh, that's very simple to answer: P is not an element of NP. The question people care about is whether there's any element in NP that's not in P. In LaTeX notation P \subset NP vs P \subseteq NP.
I'm not sure what you mean by ill-posed? The question is very clear. What are you trying to say?
There are many ways it might turn out to be ill-posed, this is just one of them. Impagliazzo's "5 worlds" survey is in some sense a catalog of some of these ways, and includes some of the ways you seem to be referencing (approxmations, probabilistic techniques, average-case efficiency; depending what you mean this could lie in the "Heuristica" world).
OK, that's a reasonable worry and one that practitioners share. Thanks for explaining. Though I don't think ill-posed is a good term for this, the technical meaning of the term points in a different direction.
So far, as far as I can tell this new result gives much of any extra credence to that worry.
The problem is that this formal question might not correspond to the informal question we actually care about.
I'm also confused what you are saying down here. Though I can see how "sub-exponential" is easily misleading terminology.
With code, there's always plenty of bugs, hacks, quick "temporary" solutions, etc. But in math, a proof either exists or it doesn't and they can always be automatically verified using tools like Lean.
> 10^87 variables, a point where the proposed new method surpasses the already existing sat solvers
Yeah, it's not efficient in the ordinary sense.
Considering that no human will be able to sift through these in no less than a team-decade, to verify that there's no mistake, yet still that will be massively less compute than the one necessary to produce the 'solution', isn't the empirical finding contrary to the theoretical finding being suggested? Namely that in practice we are generating these 'proofs' in a massive amount of compute time, but it will take tiny amounts of time to verify them.
Is it very useful to talk about computing in purely mathematical terms and not in empirical terms? There's very obvious truths that we are seeing here, and it seems like those that go through some sort of rigorous mathematical training kind of fail to see it. Similar to how 70% of physicians or something believe in the Many Worlds Interpretation or that time isn't real, a sort of algebraic psychosis where one is removed from a human reality that we have access to in order to attempt getting close to an 'objective reality' that is far removed from the human experience.
To some extent we are computing entities, so I don't even think that we can conceive of computing as decoupled from ourselves[1]. I know the observer effect is very often mis-cited by laymen, but I'll be damned if some computer scientists like Godel don't sound like they were up to something similar to this.
Also, here's another outsider perspective. This is obviously slop, I'm not sure how but it's obviously nerd-sniping the CS majors that understand this, because it's obviously very hard to find the flaw, but it gives epicycles energy. It's also sufficiently complex that under a bayesian analysis it is more likely that the AI has reached the limit of its processing power until it becomes confused enough to believe it has reached something significant, kind of like how I'm doing now.
[1] xkcd://1163
How do you figure that? For ETH, OpenAI is engaging with top experts in this area. It's unlikely that they'll need 10 man-years combined to go through the results:
> This work will be verified and shepherded by a group led by Russell Impagliazzo (UC San Diego), Ramamohan Paturi (UC San Diego), and Ryan Williams (MIT). All three are experts in algorithm design and complexity theory.
> Impagliazzo and Paturi, along with Francis Zane, are the original proposers of the Exponential Time Hypothesis, and have authored a number of influential papers on the topic over the last 30 years.
> Williams has refuted strong versions of the ETH, used ETH for hardness results, and connected algorithms and lower bounds.
From the HN comment guidelines:
> Don't post generated text or AI-edited text. HN is for conversation between humans.
Disclosure doesn't address the objection (not that it wouldn't be obvious anyway). If you learned something from an AI convo, tell us what you learned, in your own words, not what the LLM said.
They are making good progress on similar research programmes for many cetaceans.
In the case of our stochastic parrots it's even easier, since they already speak something like human language. And for the math proofs it's even easier, because once they are formalised into something like Lean the humans only need to understand the statement of the theorem, and a mechanical computer program can check the proof.
It is not a demerit, actually I think that it is a very elegant outcome how many problems could be solved by generation and this probably show us how language is a far more important thing than we ever thought it was.
It's not possible for someone who's not a specialist in the field to understand it (unless there are more elementary proofs, of which likely none exist).
siting on a recliner making an occasional sensible chuckle while flipping through the pages?
OpenAI has that too - open their website and ask.
I totally disagree with you on the precept that all difficult to understand things need be needlessly dumbed-down/watered-down until palatable for a mass (average) audience. Requiring 'math50' before 'trig101' isn't gate-keeping in any moral sense, it's an effort to save everyones' time involved when the effort is futile.
Similarly I don't demand that haute couture fashion companies explain the style to me until 'I get it' ; I just take it for granted that i'm not going to be able to understand the entirety of the world in one lifetime.
Why? The investors can just ask Claude or Gemini whether the proof holds up.