The Exponential Time Hypothesis Is False [pdf]
See also: Announcing three new discoveries in mathematics, computer science, and physics - https://news.ycombinator.com/item?id=50251344
See also: Announcing three new discoveries in mathematics, computer science, and physics - https://news.ycombinator.com/item?id=50251344
j / k
|
Down or up a comment |
h / l
|
Previous or next link |
?
|
This help |
- 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.
Given the current developments, I would not be confident that it would not lower dramatically pretty soon.
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.
…Oh, I see. The M here is a hypothesized constant, with n as the base. That's how polynomial time looks. Exponential time would have n in the exponent.
> 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.)
Edit: Ok, I a guess I am wrong if the reduction is n^ log n/(log log n)^2 we are back to exponential.
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.
I'm not trying to argue there is a single cause, either (sorry if my either-or phrasing implied that). I think attributing any general feature of an academic discipline to a single cause would be missing a dozen other contributing factors.
Of course three letter agencies are watching this carefully, and I'd believe they were weighing in somehow, as they have in cryptography in the past. My point was that we shouldn't ignore the overall sparsity of funding in pure math and science projects. A lot of (probably most) contributors to bleeding-edge research have a number of other jobs in their position.
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.
> 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.
> Our result is purely asymptotic: for arbitrary 3-CNF formulas with m = 5n clauses, the bound we prove does not improve on the 2n of exhaustive search unless n > 10^10000,
So their algorithm beats standard algorithms only when you have more variables than there are atoms in the universe (10^80). Even if every atom contained a whole universe, and each atom in each universe itself contained a whole universe, iterated 100 times, your still not there.
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.
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?
Jokes aside, by then we're gonna have StarTrek Replicators. Exciting!
sure, this proof itself doesn't settle the P/NP problem, but we've lost one of our core beliefs.
https://news.ycombinator.com/item?id=50255159
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
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.
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.
[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.
— Scott Aaronson
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?
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.
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.
However, so far equating P with 'efficient in practice' seems to hold up.
I'm also confused what you are saying down here. Though I can see how "sub-exponential" is easily misleading terminology.
In essentially all cases, we have no real reason to believe or disbelieve. We choose these bounds because we can't do better. It's often the case that we later prove them wrong with some extremely strange result. Here, we have weird bounds for 3-SAT, and a few weeks ago we had one for integer multiplication.
But this has also happened repeatedly throughout history. In the 50s Kolmogorov conjectured that n-bit integer multiplication was \Omega(n^2). Karatsuba produced O(n^{1.58}) during Kolmogorov's seminar on the topic. Strassen discovered matrix multiplication is O(n^{2.81}) while trying to prove it is O(n^3). And on and on and on.
Maybe P and NP are well-formulated and they do perfectly capture our intuition of "efficient" and "efficiently verifiable" algorithms. Or maybe they don't. We are probably going to keep finding extremely weird, cheesed-out bounds for famous problems, though. You can choose what you want to believe, but I think it would be more remarkable if the reality of P and NP turned out to be as clean as the bounds indicate.
It is true that CS had to make theoretical concessions. Just as Newton did. We don't criticize Newtonian mechanics (or, I don't know, Galileo?) for not being realistic about friction or idealized balls rolling down ramps. Their anti-empiricism was a starting point for physics.
To wit, the mathematical rationale for P-NP was precisely that that under polytime reduction this is still closed in P. That is a very reasonable starting point for a theory. This is also the reason why it is tripping up a large swath of the comment thread with people asking about subexponentials which do not preserve that closure
The opposite narrative is that in science, these idealizations yield profound intuitions and insights.
Furthermore, how far are you willing to go? Do you think Turing machines are invalid, that Turing-equivalent computation is pointless and unrealistic? So we are never allowed use that theory to convey the essential idea of in principle all computers being fundamentally functionally the same and that anything claimed to be more powerful than that had better have some incredible evidence, lest it be appeal to magic. Computability and complexity have a shared foundation so how much of that foundation are you going to reexamine?
Whereas if one wishes to be like a covert finitist/intuitionist, they ought to be open about that instead of accuse asymptotic complexity (or analgously, Turing computability as above) of trying to "cheese" complexity theory as a research programme. Meanwhile, it is true that P vs NP could have large exponents or constants in P, e.g. O(c*n^100...), literally this is the first thing taught in any complexity course or textbook. Students and practitioners remember this admonition well, maybe they just don't talk about it publicly as much.
One can go even further back. Cantor was marginalized for his ideas about infinities.
The difference with people like Lipton, and Knuth, is that the critique is coming from inside the house. In that they know the theory and the importance of it, but also hope/aspire for some new way to address the open question. They are keenly aware that P / NP is a problematic question, but not for lack of trying or stupidity on the part of other scientists. What is more likely is that the 21st/22nd century math to pose the better question does not exist yet (or may never be accessible to humans, another question well on the minds of many today).
Here's something to ponder. It is often observed that despite being NP-complete, many actual human instances are in fact tractable. E.g. routine airline scheduling depending on SAT solvers. But is this evidence that NP-completeness is a wrong theory or evidence that human-sized problems are a special case that becomes tractable (anthropocentrism), or some other more complicated reason?
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.
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.
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'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?
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.
OpenAI has that too - open their website and ask.