Posted by vok 9 hours ago
- 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 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.
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.
It also not probabilistic, so linear programing is not rely a good example
> 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.
https://www.informit.com/articles/article.aspx?p=2213858&WT....
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)
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.
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.
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.)
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)
> 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?
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.
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.
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.
sure, this proof itself doesn't settle the P/NP problem, but we've lost one of our core beliefs.
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?
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.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.