This author seems to really mis-understand complexity theory and in what ways it matters. The choice of exponential = bad and polynomial = good may have been quasi-arbitrary initially, but it since found a much more solid footing.
Exponential complexity is what you automatically get when your algorithm is "generate a possible solution, verify if it's correct, repeat if it's not". Polynomial complexity is what you get when the problem itself has some kind of structure that you can exploit to either directly construct a solution, or to generate a very small set (relative to the problem size) of possible solutions that have to be checked by hand.
Now, it is true that for all practical problem-solving purposes, "P = NP but only with algorithms that require n^10^80 or more time (with this as a proven lower bound for even the typical case, no hope of improving)" would be exactly equivalent to "P != NP". However, it would still be a mathematically extremely interesting result, as it would tell you that any problem where it is easy to verify if a solution is correct carries some hidden structure that makes it "easy" to generate the solutions. And it could still open the door to finding new sub-classes of actually easy instances of these problems that are not known today, even if the worse case remains just as intractable.
Now, note the refutation of ETH with the new algorithm found by AI is not really that impressive, it doesn't seem to have that deep of an implication. Sub-exponential running times are not that fundamentally different from exponential ones - they basically just tell you that the problem has just enough structure to eliminate a certain class of possible solutions outright, instead of spending the time to actually verify them. If the algorithm found had been polynomial, even of a huge degree, this would have been a completely different discussion. As it is, we'll just replace the ETH with a "nearly-E"TH and nothing much changes.
Moreover, it was already known that some NP-complete problems admit sub-exponential algorithms. For example, planar graph 3-colorability can be solved in 2^O(sqrt(n)) time. This is not only sub-exponential, but vastly better than the running time of the new 3-SAT algorithm.
Still, the result is very interesting, since many problems can be solved asymptotically faster once subproblems that can be represented as 3-SAT can be solved faster. For example, we now have now have a deterministic interger factoring algorithm with run time N^o(1), where N is the integer being factored. Heuristic algorithms already achieved this bound, but the new claim is a deterministic worst-case guarantee. The result is a fairly straightforward application of the new 3-SAT solver.
> Moreover, it was already known that some NP-complete problems admit sub-exponential algorithms. For example, planar graph 3-colorability can be solved in 2^O(sqrt(n)) time. This is not only sub-exponential, but vastly better than the running time of the new 3-SAT algorithm.
I'm not real good at these sorts of details, but I'm struggling more than usual here. From what you say, and from things I think I know:
* Planar graph 3-colouring (P3COL) is NP-complete;
* Therefore 3-SAT can be reduced in polynomial time to P3COL;
* There is an algorithm for P3COL that runs in 2^O(sqrt(n)) time;
* Therefore there is an algorithm for 3-SAT that runs in 2^O(sqrt(n)).
> For example, we now have now have a deterministic interger factoring algorithm with run time N^o(1), where N is the integer being factored. Heuristic algorithms already achieved this bound, but the new claim is a deterministic worst-case guarantee. The result is a fairly straightforward application of the new 3-SAT solver.
This can't be true unless you're talking about unfathomably large integers, since the new 3SAT algorithm only improves on the 2^n bound for n > 10^100000000. That is, it's not in any way a practical algorithm that will ever be runnable on any possible computer.
> Exponential complexity is what you automatically get when your algorithm is "generate a possible solution, verify if it's correct, repeat if it's not".
I might be misunderstanding you, but this surely depends on the size of the candidate set in the problem. For a problem like "determine whether a given list of integers of length `n` contains a pair that sum to 100" the naive brute-force algorithm is polynomial. If you replace "pair" by "subset" then the naive brute-force algorithm becomes exponential.
Yes, I should have been more careful with the wording. Some problems have polynomial numbers of possible solutions, so for those there is no discussion of this kind. The more important point is that for some problems with a more-than-polynomial solution space (since even exponential is not precise enough, the solution space can be more than polynomial, such as n! for traveling salesman) we still have polynomial solutions, whereas for others we do not know of such algorithms.
The question can actually be generalized further - is it the case that for any solvable problem it's possible to find a solution without verifying every possible solution, and more specifically, only a tiny subset of the solution space? This would apply even beyond P vs NP, the same question would arise for EXP vs NEXP (that is, problems where we can find a solution vs just verify a given solution in exponential time), and same for factorial or Ackerman or any other complexity we want to imagine.
Looking at the problem in this way should also make it easier to construct a more strictly practical version of P vs NP, though it actually gets much harder to pin down details. That is, we can construct complexity classes that better match "what is plausibly solvable with a real computer" vs "what is plausibly verifiable with a real computer" and ask a similar question: given any problem of the second kind, can there be any generic algorithm of the first kind that would solve it?
Maybe I'm reading a bit too much into it but knowing it is NP (i.e. can be verified in polynomial time by a Turing machine) means it can be solved in polynomial time by a nondeterministic turing machine and there's at worst 2^N branches in it. Sort of. Giving a naive expectation of 2^N runtime times some polynomial. Which is exponential.
> However, it would still be a mathematically extremely interesting result, as it would tell you that any problem where it is easy to verify if a solution is correct carries some hidden structure that makes it "easy" to generate the solutions.
Your ""easy"" here means actually hard, not easy at all, so I don't think this is any evidence that it would be "extremely interesting".
And that's actually a point of the article: some problem being solvable by a polynomial algorithm was originally only interesting insofar it was a proxy for being easy. We were interested in easy solvability, not polinomiality itself. But now the proxy has mutated into an optimization target.
I’ve seen quite a few critiques of the practicality of time complexity analysis but I’ve never seen an article describe what we should replace it with. Time complexity analysis, as given, has given some structure to the infinite zoo of problems even if imperfect and composes relatively nicely and is relatively simple. It’s also tractable, has mathematical structure, and is often practical as a heuristic (the kinds of algorithms people typically encounter or come up are typically reasonable under this kind of analysis). In order to be a proper substitute, something would have to satisfy all these qualities. Without such a substitute, we are back to analyzing problems and their complexity without any sort of framework which seems even worse than just remembering that sometimes the big O is not practical.
The only candidate that would be more practical that I know of is cache complexity for cache oblivious algorithms but that’s much more complicated.
> I’ve seen quite a few critiques of the practicality of time complexity analysis but I’ve never seen an article describe what we should replace it with.
The correct notion of "efficient" being not precisely defined is not a reason or excuse to narrowly focus on a precise but incorrect definition of efficiency. The property of being correct is more important than the property of being precisely defined.
Satisfying a precise definition is only useful and interesting insofar it clarifies the underlying notion of efficiency, and in cases where it doesn't (as in "galactic" algorithms) satisfying the precise definition doesn't bestow interestingness on the algorithm.
I'm frustrated with these "galactic algorithm frustration" posts
big constants are not new. We all had a laugh when matrix mul exponent went from [2.3728]639 to [2.3728]596
Even more than that - reading GMP manual and seeing all the "more efficient, but bigger constant" algorithms take over each other as the size grows causes *awe*
so this "sudden" discovery that theory is different from practice has been bloody obvious for everyone. I'm more inclined to say "if you want to went frustration at Ai - do that, stop showing your ignorance"
---
the main benefit for these results isn't to show what's possible - it's to show what's *not impossible*
---
also I just saw that this is the same author that wrote "Did I read this paper? Of course not. No one at OpenAI read this paper either, so why should I?"
so he expects same level of discussion he deserves himself - completely negligible
>> also I just saw that this is the same author that wrote "Did I read this paper? Of course not. No one at OpenAI read this paper either, so why should I?"
You can excuse his, I would do that, given the absurdity of this "big" mathematical problems driven marketing campaign by the ghouls.
>> so he expects same level of discussion he deserves himself - completely negligible
The ideas are shared by a not too few people in CS/Eng/Math, probably because there is actually a vagueness of what's (exactly) the role of Complexity Theory, did the pioneers of CT have the slightest idea that the field would drift into "just find some galactic algorithm for this generic problem, ok?"? idk.
> We all had a laugh when matrix mul exponent went from [2.3728]639 to [2.3728]596
Indeed. But the frustrating thing remains. Obviously animal and human brains do something similar, and obviously it's not even N^2, because anyone can count inputs and outputs for our brains, calculate N^2 and even at picowatts per operation that is just not happening ...
1000 Hz, ~800 input nerves, 20W power usage => 800 000 input values per second, squared, would leave 0.03 nW per input value. That's not enough to turn the handle on a single protein, so that's not happening. That's not enough to propagate the result of the calculation within a cell. A 2.3 power is out of the question.
One imagines maybe you can get to N^1.4 within that budget for whatever the brain is doing. Maybe. But that would be the limit.
„Something similar” can completely change asymptotic bounds though. Compare for example Integer Linear Programming and normal Linear programming. They look “very similar”, but there is an exponential worst case gap (unless P=NP).
About ETH: Many people say now that ETH was simply stated in a too strong manner, and that the correct exponential time hypothesis is SH, the Satisfiability Hypothesis.
It is almost the same as ETH, but allows for non-polynomial improvements in the exponent (which is what was proved by Clause/ChatGpt).
> About ETH: Many people say now that ETH was simply stated in a too strong manner, and that the correct exponential time hypothesis is SH, the Satisfiability Hypothesis.
In 3 months: some AI frontier lab will disprove SH.
There is literally not one aspect of the universe that is provably finite. Not in any direction, not at any scale, not in any way you can think to look at it.
Maybe I misunderstand you, but I don’t think I agree with that.
E.g. the observable universe is finite. Its observable age is finite. The number of known elementary particle types is finite. The number of particles within the observable universe is finite (according to the current understanding). Etc.
There are many examples.
Do we disagree on this, or am I perhaps misunderstanding your position here?
Key word is provably. We can assume the universe is finite because we don't have evidence against it, but no one knows if it's possible to prove or reject that for good.
Infinity is an abstraction. The universe cannot be "infinite" in the mathematical sense, as the mathematical infinity is an abstraction. The only meaningful question is "is mathematical infinity required to produce good models of the universe/physics?" and the answer so far is "no". We use infinity because it is convenient, but it is not really needed.
There is no reason to think that "infinity" will be essential to describing the universe any more than any other possible abstraction that we have not so far constructed.
> The universe cannot be "infinite" in the mathematical sense
Why not? An infinitely large universe goes against our intuitions, but our intuitions were formed by the experience of living on a finite planet and have no bearing on what's true on a galactic scale – just like they have no bearing on what's true at the quantum scale. There is no objective reason to assume that the universe isn't infinite.
I would say that there is nothing in intuition that goes against infinities, really. Quite the opposite, eg most ancient greek philosophy assumed matter could be divided indefinitely while retaining its properties. It was scientific and mathematical development that actually showed that finite/discrete models are enough to describe physics.
Moreover, even if finitism is not enough, as I said in mathematics infinity is specific concepts/abstractions, and there are even infinities with different cardinalities, not to mention the axiomatic system within which it is defined produces different properties of infinity. Which infinity is the universe of all these? I am not even sure if this question can be really meaningful, unless we get to a completely different description of the universe than the ones we have where such statements can actually make sense. The best we can get imo is to show that some accurate physical model requires infinity, and that seems already quite hard thing to show.
Observable universe is just the part of the universe from where light had time to hit the Earth already. It is growing pretty much at the speed of light, not because of physical changes to the space-time, but because the light from farther away finally arrived. So while it's definitely finite, I wouldn't say it disproves the claim that nothing about the universe is known to be finite.
Because of inflation, there is a distance at which the objects not already in our light cone are moving away faster than the speed of light. So the amount of stuff that we will be able to observe is limited.
besides the other points raised, even within the observable universe there are some assumed infinities as well as things that might be infinite, might not be.
e.g. time and space likely aren't quantized, you have an infinite amount of points in between any two arbitrary points in spacetime. don't mention planck scale black holes, it's a meme and even most phycisists who like to cite it haven't actually thought about it for more than 5 minutes.
I have the exact opposite experience. There nothing I can think of that is infinite in nature. Not only is it impossible to prove infinity empirically ("in the universe"; the only thing that actually matters) but there are exactly zero actual things with an infinite nature of any kind that I can think of. It's a useful imaginary construct that makes fancy math work, that's all.
For example, the special theory of relativity doesn't work if space-time has any "lowest scale" (i.e. if the distance between any two events can be expressed as n * min_dist, where n is an integer and min_dist is a constant that has the same value for all observers), it you can't infinitely sub-divide it, since then lengths couldn't contract the way that the Lorrentz transforms predicts. Lots of math in QM and QFT also requires space and time to be continuous for other reasons as well.
Also, none of our current laws put any kind of limit on the life span of the Universe as a whole, so space-time is also infinitely increasing, even if heat death or big crunch models are correct.
Of course, none of this is provable per se - it is fundamentally impossible to run an experiment in finite time that proves whether something is finite or infinite. It could be that SR and QFT are wrong in their continuous space assumptions, but only in ways that are too subtle to measure. Still, as it stands, we don't have any theory of how the world works which allows for a discrete space-time, even as an approximation - we need space-time to be continuous for our current theories to work at all.
Well, our physics is famously incomplete and even if it weren't: math needing infinity is in no way shape or form proof of anything but the nature of math which itself could be nothing but a highly particular construct.
I always find it interesting nobody seriously questions why something so extraordinarily basic as geometry pervades "the universe". I'd say it's much more likely we are mathy creatures and cannot do anything but perceive logical building blocks somewhat reminding me of a guy using a flashlight proclaiming the universe comprises various configurations of spherical lights.
I can imagine infinity just fine and I'm sure many useful things can be inferred from it, but that doesn't mean it exists. Lots of math is possible but does not exist in reality and that's fine, I'm just being honest about the very real boundaries here. I get the feeling many people confuse the map for the territory.
> there are exactly zero actual things with an infinite nature of any kind that I can think of
That's because your imagination is bounded by being a monkey that has spent its entire life in a finite environment — no offense. The universe, however, isn't bounded the limits of our imagination or intuition.
Yes, that's all very interesting (truly) but where does your actual lived experience come into play? That's the part I am talking about, the "in the universe" part, not the "could be" or "in imaginary parts of the possible universe" but the actual, experience-able universe. That's what separates math from physics and IMO math is the one that has to prove its worth not the other way around. I can construct endless internally consistent imaginary worlds with zero bearing on (any) reality.
And not one aspect that’s provably infinite, either, sl I don’t think your argument is interesting.
There are many things about the universe, though, that are finite to the best of our understanding. As in, any infinities that crop up in our models are properly understood to be cases where the models are wrong or incomplete.
On the other hand, every single observation anyone has ever made was a finite value of something.
Even when things are potentially infinite, there seems to be a conspiracy of the universe to make it finite. The size of space may be infinite, but due to a finite speed of light and the finite age of the universe we can only ever observe a finite slice. When attempting to zoom in to an infinite degree onto supposedly point-like particles, quantum mechanics makes everything fuzzy and finite again. Black holes appear to have infinite curvature at the center, but it's unobservable due to the event horizon.
This principle seems so natural that we even apply it in advance: In quantum field theory, there are infinities in the equations when done naively, which we deem so unnatural that we apply funny tricks which make mathematicians cringe, but they miraculously work out so well that we get theory and experiments to agree to an astonishing degree.
And yet the vast majority of physicists treat infinity in the equations as a sign of them being incomplete, and dismiss the possibility of the universe being infinite in any way
I would like to point out that there is also no proof of God not existing either
Who needs calculus anyways? I'd rather focus learning linear algebra especially after realizing a derivative is just a linear transformation and integration problems share a lot with determinants (areas).
Maybe so many more people would engage with mathemathics when they realize this.
I can't really think of anyone. Maybe just mathematicians, physicists, economists, computer scientists, chemists and engineers. Apparently they even use something called back propagation in AI training, which is nothing but chain rule from ... calculus.
But yeah, I can't see it being relevant since we have linear algebra already.
Maybe you missed my point but I was talking about calculus in the theoretical sense i.e study of functions in the reals.
In every way you are referring to people using calculus in an applied sense always been reliant on linear algebra.
Python libraries for doing backpropagation is built on numerical techniques that computes and is definitely not just manipulating symbols and calling it chain rule.
No, back propagation is just the chain rule from calculus. d(f(g)) = df(g)dg. It is applied to linear algebra, but with linear algebra alone you will never arrive to it.
You can just admit you don't understand calculus (and go and learn it if you care). No reason to go around doing mental gymnastics about it.
Good luck optimizing without being able to use the condition f'(x) = 0. You might think you can do everything numerically, but when your function has parameters you're in trouble.
Geez, I don't know why I keep arguing with you people. I've seen several examples where just integrating or derivating something gets you an analytic solution that you can compute in an instant, rather than having to start doing some 3 dimension integrals numerically.
It would be great to prove that there is or isn't a non-galactic polynomial-time algorithm for NP-complete problems. But we can't even solve the easier problem of proving there is or isn't a galactic polynomial-time algorithm, so what hope is there for the harder problem?
If you could prove that any polynomial-time algorithm for NP problems had to be galactic, you would be the most celebrated computer scientist since Turing. It's just no one has any idea how to do that.
Yep, ranting against galactic polynomial algorithms reminds me of the people who oppose the use of infinity. Like, yes, it's not physically realistic construction, but it makes things simple enough that we can do analytic solutions to problems and simplify terribly complicated things.
Polynomials are closed under multiplication, so you can do a poly algorithms poly number of times and still have a poly algorithm. That's very convenient.
The article makes the point that not all polynomial algorithms are created equal. If you combine ten O(n^2) algorithms, you can end up with an O(n^1024) algorithm, which isn’t practical anymore, despite being polynomial. That’s inconvenient.
> Applied mathematicians often need to build a giant scaffolding of mathematical modeling to solve a problem. This scaffolding creates new mathematical puzzles that aren’t directly connected to the original problem of interest, but that entice problem solvers. You’ll then see dozens of follow-up papers solving the puzzles but forgetting the problem we cared about in the first place.
really resonated with me. The pure math tail is wagging the applied math dog.
Applied math wants to solve a practical problem. It wants to do something that will actually matter in the real world somewhere.
Pure math wants to understand. It doesn't care about practical application. But we still want it to do well and thrive, because it makes the tools that applied math has available, and when you have a practical problem, that matters.
It's just irrelevant for big-O complexity what happens for instances below a constant threshold, so the algorithm uses the simplest approach and moves on. If you have an exponential-time algorithm that's faster than brute force for small instances, you can use that and get a faster overall runtime at the same big-O complexity. If you can lower the switchover threshold, ditto. It's a bit weird to dismiss the subexponential algorithm just because it's leaving an obvious optimization on the table... it can only get faster from here.
This reminds me of the (perhaps unrelated meme) hello I would like (graph of zeta function) number of apples. Statements dreamt up by the utterly deranged.
Indeed I have met professors who claim since something is O(1) it doesn't matter if you run it 4 times. No need to optimize. I think it's just part of the wider divide between theory and application. For instance big O also requires a register machine to make sense, which most courses don't define. Somehow addition and multiplication are O(1) in some places and O(n) or O(n^2) somewhere else. Also quite common is the fact that sets are slower than lists for lookup for small n, despite being O(1).
It's just a tool and we shouldn't miss the trees for the forest. I also understand this comment has nothing to do with the ETH or the article, but just some thoughts I have after reading the first chunk on complexity
Did you ever pause to consider that theoretical computer science might not be done for the sake of midwit code monkeys whose deepest contact with complexity theory was when they learned to reverse a linked list in O(n) for their SWE interview?
I'm not sure that retreating to the ivory tower is a winning rhetorical strategy.
Not sure why the hostility anyways. If appreciating TCS results really is a higher brow activity, then GP's indignation at computational models shouldn't upset you, quite the opposite. It's definitionally the normal experience.
And while I do find the blogpost in the OP trite, that is mostly because it's from someone who should absolutely be more intimate with the subject than such "midwitted code monkeys" (aka. normal people) you refer to, yet pretends to feel duped by OAI's results. Quite the different case, and I think is much more worthy of ridicule as a result. They're the high brow who should be appreciating, understanding, yet fail to.
I think the common expression is to miss the forest (big picture) for the trees (details). But maybe you're playing on words and saying we shouldn't let the big picture (big O notation/analysis) obscure our attention to the details (an algorithm's actual efficiency and performance).
I guess in engineering what you care about is: how fast is it on given input size X relevant for the practical problem. Or: how much input size can we do in time bound Y.
I don't think the author's criticism of "Big-O Cabal" is very nuanced, but to the second half of the essay it is funny/concerning/sobering to find that the OpenAI proof is doing brute-force search for all instances below some super-astronomic threshold. It kind of buries the lede if the proof did not mention this clearly and the author has to comb through it to find out (I asked ChatGPT the same on the pdf file, but it came up with some other threshold number).
I don't think it matters? It's completely standard for "galactic" algorithms and not relevant to big-O runtime.
The complaint that these algorithms aren't "realistic" is ostensibly valid, but you could just as well aim that cannon at 95%+ of math research too. Complexity theory is interesting and fun. Isn't that enough?
> It's completely standard for "galactic" algorithms and not relevant to big-O runtime.
This is true, but if doing brute-force search for all instances below some super-astronomic threshold is part of the algorithm, you typically want to understand
- where this constant comes from,
- how much this constant can be decreased (or why it can't)
- etc.
So, proving the correctness of an algorithm which is doing brute-force search for all instances below some super-astronomic threshold is typically just the first step towards getting an understanding of the complexity-theoretic phenomenon.
So: There is indeed nothing wrong with such aspects of galactic algorithms, but exactly understanding and improving the super-astronomic thresholds involved is the next step.
I hate to use absolutely but it absolutely does matter from an education perspective. To put things in perspective to a layperson explain to them this particular galactic theorem requires full search below some titanic |x|. That should prompt some excellent lay questions that a serious computer scientist ought to reckon with.
It is not to say the approach has been wrong (as the author strongly believes in his reframing) but that this clarity does matter for purposes of, ahem, mathematical understanding.
Author is a math professor who somehow wants you to believe that he didn't know what a computational model is until OpenAI's manuscript dump a few days ago. In this post, he now extends that pretending game to galactic algorithms.
Very gonzo, but maybe I prefer to learn about these things with a little less circlejerk.
This author seems to really mis-understand complexity theory and in what ways it matters. The choice of exponential = bad and polynomial = good may have been quasi-arbitrary initially, but it since found a much more solid footing.
Exponential complexity is what you automatically get when your algorithm is "generate a possible solution, verify if it's correct, repeat if it's not". Polynomial complexity is what you get when the problem itself has some kind of structure that you can exploit to either directly construct a solution, or to generate a very small set (relative to the problem size) of possible solutions that have to be checked by hand.
Now, it is true that for all practical problem-solving purposes, "P = NP but only with algorithms that require n^10^80 or more time (with this as a proven lower bound for even the typical case, no hope of improving)" would be exactly equivalent to "P != NP". However, it would still be a mathematically extremely interesting result, as it would tell you that any problem where it is easy to verify if a solution is correct carries some hidden structure that makes it "easy" to generate the solutions. And it could still open the door to finding new sub-classes of actually easy instances of these problems that are not known today, even if the worse case remains just as intractable.
Now, note the refutation of ETH with the new algorithm found by AI is not really that impressive, it doesn't seem to have that deep of an implication. Sub-exponential running times are not that fundamentally different from exponential ones - they basically just tell you that the problem has just enough structure to eliminate a certain class of possible solutions outright, instead of spending the time to actually verify them. If the algorithm found had been polynomial, even of a huge degree, this would have been a completely different discussion. As it is, we'll just replace the ETH with a "nearly-E"TH and nothing much changes.
Moreover, it was already known that some NP-complete problems admit sub-exponential algorithms. For example, planar graph 3-colorability can be solved in 2^O(sqrt(n)) time. This is not only sub-exponential, but vastly better than the running time of the new 3-SAT algorithm.
Still, the result is very interesting, since many problems can be solved asymptotically faster once subproblems that can be represented as 3-SAT can be solved faster. For example, we now have now have a deterministic interger factoring algorithm with run time N^o(1), where N is the integer being factored. Heuristic algorithms already achieved this bound, but the new claim is a deterministic worst-case guarantee. The result is a fairly straightforward application of the new 3-SAT solver.
> Moreover, it was already known that some NP-complete problems admit sub-exponential algorithms. For example, planar graph 3-colorability can be solved in 2^O(sqrt(n)) time. This is not only sub-exponential, but vastly better than the running time of the new 3-SAT algorithm.
I'm not real good at these sorts of details, but I'm struggling more than usual here. From what you say, and from things I think I know:
* Planar graph 3-colouring (P3COL) is NP-complete;
* Therefore 3-SAT can be reduced in polynomial time to P3COL;
* There is an algorithm for P3COL that runs in 2^O(sqrt(n)) time;
* Therefore there is an algorithm for 3-SAT that runs in 2^O(sqrt(n)).
That doesn't feel right ... where is the error?
Say the polynomial reduction is P(n)=n^2 then the algorithm for 3-SAT is 2^O(sqrt(P(n))) = 2^O(n)
Gotcha ... thank you.
Now I need to digest the implications of that, and I need to find the algorithm for P3COL.
I need a coffee ...
> For example, we now have now have a deterministic interger factoring algorithm with run time N^o(1), where N is the integer being factored. Heuristic algorithms already achieved this bound, but the new claim is a deterministic worst-case guarantee. The result is a fairly straightforward application of the new 3-SAT solver.
This can't be true unless you're talking about unfathomably large integers, since the new 3SAT algorithm only improves on the 2^n bound for n > 10^100000000. That is, it's not in any way a practical algorithm that will ever be runnable on any possible computer.
I'm reading O(1.3289^n) for 3-colorability.
> Exponential complexity is what you automatically get when your algorithm is "generate a possible solution, verify if it's correct, repeat if it's not".
I might be misunderstanding you, but this surely depends on the size of the candidate set in the problem. For a problem like "determine whether a given list of integers of length `n` contains a pair that sum to 100" the naive brute-force algorithm is polynomial. If you replace "pair" by "subset" then the naive brute-force algorithm becomes exponential.
Yes, I should have been more careful with the wording. Some problems have polynomial numbers of possible solutions, so for those there is no discussion of this kind. The more important point is that for some problems with a more-than-polynomial solution space (since even exponential is not precise enough, the solution space can be more than polynomial, such as n! for traveling salesman) we still have polynomial solutions, whereas for others we do not know of such algorithms.
The question can actually be generalized further - is it the case that for any solvable problem it's possible to find a solution without verifying every possible solution, and more specifically, only a tiny subset of the solution space? This would apply even beyond P vs NP, the same question would arise for EXP vs NEXP (that is, problems where we can find a solution vs just verify a given solution in exponential time), and same for factorial or Ackerman or any other complexity we want to imagine.
Looking at the problem in this way should also make it easier to construct a more strictly practical version of P vs NP, though it actually gets much harder to pin down details. That is, we can construct complexity classes that better match "what is plausibly solvable with a real computer" vs "what is plausibly verifiable with a real computer" and ask a similar question: given any problem of the second kind, can there be any generic algorithm of the first kind that would solve it?
Maybe I'm reading a bit too much into it but knowing it is NP (i.e. can be verified in polynomial time by a Turing machine) means it can be solved in polynomial time by a nondeterministic turing machine and there's at worst 2^N branches in it. Sort of. Giving a naive expectation of 2^N runtime times some polynomial. Which is exponential.
> However, it would still be a mathematically extremely interesting result, as it would tell you that any problem where it is easy to verify if a solution is correct carries some hidden structure that makes it "easy" to generate the solutions.
Your ""easy"" here means actually hard, not easy at all, so I don't think this is any evidence that it would be "extremely interesting".
And that's actually a point of the article: some problem being solvable by a polynomial algorithm was originally only interesting insofar it was a proxy for being easy. We were interested in easy solvability, not polinomiality itself. But now the proxy has mutated into an optimization target.
I’ve seen quite a few critiques of the practicality of time complexity analysis but I’ve never seen an article describe what we should replace it with. Time complexity analysis, as given, has given some structure to the infinite zoo of problems even if imperfect and composes relatively nicely and is relatively simple. It’s also tractable, has mathematical structure, and is often practical as a heuristic (the kinds of algorithms people typically encounter or come up are typically reasonable under this kind of analysis). In order to be a proper substitute, something would have to satisfy all these qualities. Without such a substitute, we are back to analyzing problems and their complexity without any sort of framework which seems even worse than just remembering that sometimes the big O is not practical.
The only candidate that would be more practical that I know of is cache complexity for cache oblivious algorithms but that’s much more complicated.
Implicit Computational Complexity deserves to be more well known.
Why? I'm not being glib here, but I don't see what it really changes fundamentally that makes it noteworthy except as a curiosity.
> I’ve seen quite a few critiques of the practicality of time complexity analysis but I’ve never seen an article describe what we should replace it with.
The correct notion of "efficient" being not precisely defined is not a reason or excuse to narrowly focus on a precise but incorrect definition of efficiency. The property of being correct is more important than the property of being precisely defined.
Satisfying a precise definition is only useful and interesting insofar it clarifies the underlying notion of efficiency, and in cases where it doesn't (as in "galactic" algorithms) satisfying the precise definition doesn't bestow interestingness on the algorithm.
> In order to be a proper substitute, something would have to satisfy all these qualities.
Why?
I'm frustrated with these "galactic algorithm frustration" posts
big constants are not new. We all had a laugh when matrix mul exponent went from [2.3728]639 to [2.3728]596
Even more than that - reading GMP manual and seeing all the "more efficient, but bigger constant" algorithms take over each other as the size grows causes *awe*
so this "sudden" discovery that theory is different from practice has been bloody obvious for everyone. I'm more inclined to say "if you want to went frustration at Ai - do that, stop showing your ignorance"
---
the main benefit for these results isn't to show what's possible - it's to show what's *not impossible*
---
also I just saw that this is the same author that wrote "Did I read this paper? Of course not. No one at OpenAI read this paper either, so why should I?"
so he expects same level of discussion he deserves himself - completely negligible
>> also I just saw that this is the same author that wrote "Did I read this paper? Of course not. No one at OpenAI read this paper either, so why should I?"
You can excuse his, I would do that, given the absurdity of this "big" mathematical problems driven marketing campaign by the ghouls.
>> so he expects same level of discussion he deserves himself - completely negligible
The ideas are shared by a not too few people in CS/Eng/Math, probably because there is actually a vagueness of what's (exactly) the role of Complexity Theory, did the pioneers of CT have the slightest idea that the field would drift into "just find some galactic algorithm for this generic problem, ok?"? idk.
> We all had a laugh when matrix mul exponent went from [2.3728]639 to [2.3728]596
Indeed. But the frustrating thing remains. Obviously animal and human brains do something similar, and obviously it's not even N^2, because anyone can count inputs and outputs for our brains, calculate N^2 and even at picowatts per operation that is just not happening ...
1000 Hz, ~800 input nerves, 20W power usage => 800 000 input values per second, squared, would leave 0.03 nW per input value. That's not enough to turn the handle on a single protein, so that's not happening. That's not enough to propagate the result of the calculation within a cell. A 2.3 power is out of the question.
One imagines maybe you can get to N^1.4 within that budget for whatever the brain is doing. Maybe. But that would be the limit.
> One imagines maybe you can get to N^1.4 within that budget for whatever the brain is doing. Maybe. But that would be the limit.
Not for matrix multiplication of square matrices, since the output, which has to be written, is already of size O(n^2).
„Something similar” can completely change asymptotic bounds though. Compare for example Integer Linear Programming and normal Linear programming. They look “very similar”, but there is an exponential worst case gap (unless P=NP).
> Obviously animal and human brains do something similar
...what are you talking about?
About ETH: Many people say now that ETH was simply stated in a too strong manner, and that the correct exponential time hypothesis is SH, the Satisfiability Hypothesis.
It is almost the same as ETH, but allows for non-polynomial improvements in the exponent (which is what was proved by Clause/ChatGpt).
Recommended reading: https://arxiv.org/abs/2611.02650
> About ETH: Many people say now that ETH was simply stated in a too strong manner, and that the correct exponential time hypothesis is SH, the Satisfiability Hypothesis.
In 3 months: some AI frontier lab will disprove SH.
Not likely, but perhaps they prove it, thereby proving P \neq NP!
That's a very long-winded way of saying "I'm an ultrafinitist"...
This has nothing to do with ultrafinitism
Sensible position in a finite universe
There is literally not one aspect of the universe that is provably finite. Not in any direction, not at any scale, not in any way you can think to look at it.
Maybe I misunderstand you, but I don’t think I agree with that.
E.g. the observable universe is finite. Its observable age is finite. The number of known elementary particle types is finite. The number of particles within the observable universe is finite (according to the current understanding). Etc.
There are many examples.
Do we disagree on this, or am I perhaps misunderstanding your position here?
Key word is provably. We can assume the universe is finite because we don't have evidence against it, but no one knows if it's possible to prove or reject that for good.
Infinity is an abstraction. The universe cannot be "infinite" in the mathematical sense, as the mathematical infinity is an abstraction. The only meaningful question is "is mathematical infinity required to produce good models of the universe/physics?" and the answer so far is "no". We use infinity because it is convenient, but it is not really needed.
There is no reason to think that "infinity" will be essential to describing the universe any more than any other possible abstraction that we have not so far constructed.
Why can the universe not be infinite and go absolutely indefinitely in every direction?
Because only a finite amount of time passed since the Big Bang, and all speeds are finite, so it could have grown only a finite amount.
> The universe cannot be "infinite" in the mathematical sense
Why not? An infinitely large universe goes against our intuitions, but our intuitions were formed by the experience of living on a finite planet and have no bearing on what's true on a galactic scale – just like they have no bearing on what's true at the quantum scale. There is no objective reason to assume that the universe isn't infinite.
I would say that there is nothing in intuition that goes against infinities, really. Quite the opposite, eg most ancient greek philosophy assumed matter could be divided indefinitely while retaining its properties. It was scientific and mathematical development that actually showed that finite/discrete models are enough to describe physics.
Moreover, even if finitism is not enough, as I said in mathematics infinity is specific concepts/abstractions, and there are even infinities with different cardinalities, not to mention the axiomatic system within which it is defined produces different properties of infinity. Which infinity is the universe of all these? I am not even sure if this question can be really meaningful, unless we get to a completely different description of the universe than the ones we have where such statements can actually make sense. The best we can get imo is to show that some accurate physical model requires infinity, and that seems already quite hard thing to show.
Observable universe is just the part of the universe from where light had time to hit the Earth already. It is growing pretty much at the speed of light, not because of physical changes to the space-time, but because the light from farther away finally arrived. So while it's definitely finite, I wouldn't say it disproves the claim that nothing about the universe is known to be finite.
Because of inflation, there is a distance at which the objects not already in our light cone are moving away faster than the speed of light. So the amount of stuff that we will be able to observe is limited.
It makes it limited, but it doesn't make it finite.
> It is growing pretty much at the speed of light
The observable universe is growing much faster than that, because space itself is expanding.
True, my bad. It does make my point about non-finiteness of observable universe even stronger, though.
besides the other points raised, even within the observable universe there are some assumed infinities as well as things that might be infinite, might not be.
e.g. time and space likely aren't quantized, you have an infinite amount of points in between any two arbitrary points in spacetime. don't mention planck scale black holes, it's a meme and even most phycisists who like to cite it haven't actually thought about it for more than 5 minutes.
I have the exact opposite experience. There nothing I can think of that is infinite in nature. Not only is it impossible to prove infinity empirically ("in the universe"; the only thing that actually matters) but there are exactly zero actual things with an infinite nature of any kind that I can think of. It's a useful imaginary construct that makes fancy math work, that's all.
This isn't really true.
For example, the special theory of relativity doesn't work if space-time has any "lowest scale" (i.e. if the distance between any two events can be expressed as n * min_dist, where n is an integer and min_dist is a constant that has the same value for all observers), it you can't infinitely sub-divide it, since then lengths couldn't contract the way that the Lorrentz transforms predicts. Lots of math in QM and QFT also requires space and time to be continuous for other reasons as well.
Also, none of our current laws put any kind of limit on the life span of the Universe as a whole, so space-time is also infinitely increasing, even if heat death or big crunch models are correct.
Of course, none of this is provable per se - it is fundamentally impossible to run an experiment in finite time that proves whether something is finite or infinite. It could be that SR and QFT are wrong in their continuous space assumptions, but only in ways that are too subtle to measure. Still, as it stands, we don't have any theory of how the world works which allows for a discrete space-time, even as an approximation - we need space-time to be continuous for our current theories to work at all.
Well, our physics is famously incomplete and even if it weren't: math needing infinity is in no way shape or form proof of anything but the nature of math which itself could be nothing but a highly particular construct.
I always find it interesting nobody seriously questions why something so extraordinarily basic as geometry pervades "the universe". I'd say it's much more likely we are mathy creatures and cannot do anything but perceive logical building blocks somewhat reminding me of a guy using a flashlight proclaiming the universe comprises various configurations of spherical lights.
I can imagine infinity just fine and I'm sure many useful things can be inferred from it, but that doesn't mean it exists. Lots of math is possible but does not exist in reality and that's fine, I'm just being honest about the very real boundaries here. I get the feeling many people confuse the map for the territory.
> there are exactly zero actual things with an infinite nature of any kind that I can think of
That's because your imagination is bounded by being a monkey that has spent its entire life in a finite environment — no offense. The universe, however, isn't bounded the limits of our imagination or intuition.
Yes, that's all very interesting (truly) but where does your actual lived experience come into play? That's the part I am talking about, the "in the universe" part, not the "could be" or "in imaginary parts of the possible universe" but the actual, experience-able universe. That's what separates math from physics and IMO math is the one that has to prove its worth not the other way around. I can construct endless internally consistent imaginary worlds with zero bearing on (any) reality.
> There is literally not one aspect of the universe that is provably finite.
Or provably infinite.
And not one aspect that’s provably infinite, either, sl I don’t think your argument is interesting.
There are many things about the universe, though, that are finite to the best of our understanding. As in, any infinities that crop up in our models are properly understood to be cases where the models are wrong or incomplete.
On the other hand, every single observation anyone has ever made was a finite value of something.
Even when things are potentially infinite, there seems to be a conspiracy of the universe to make it finite. The size of space may be infinite, but due to a finite speed of light and the finite age of the universe we can only ever observe a finite slice. When attempting to zoom in to an infinite degree onto supposedly point-like particles, quantum mechanics makes everything fuzzy and finite again. Black holes appear to have infinite curvature at the center, but it's unobservable due to the event horizon.
This principle seems so natural that we even apply it in advance: In quantum field theory, there are infinities in the equations when done naively, which we deem so unnatural that we apply funny tricks which make mathematicians cringe, but they miraculously work out so well that we get theory and experiments to agree to an astonishing degree.
Except you I suppose.
And yet the vast majority of physicists treat infinity in the equations as a sign of them being incomplete, and dismiss the possibility of the universe being infinite in any way
I would like to point out that there is also no proof of God not existing either
Good luck with calculus tho.
Who needs calculus anyways? I'd rather focus learning linear algebra especially after realizing a derivative is just a linear transformation and integration problems share a lot with determinants (areas).
Maybe so many more people would engage with mathemathics when they realize this.
> Who needs calculus anyways?
I can't really think of anyone. Maybe just mathematicians, physicists, economists, computer scientists, chemists and engineers. Apparently they even use something called back propagation in AI training, which is nothing but chain rule from ... calculus.
But yeah, I can't see it being relevant since we have linear algebra already.
Maybe you missed my point but I was talking about calculus in the theoretical sense i.e study of functions in the reals.
In every way you are referring to people using calculus in an applied sense always been reliant on linear algebra. Python libraries for doing backpropagation is built on numerical techniques that computes and is definitely not just manipulating symbols and calling it chain rule.
How do you think they came up with backpropagation..
What a weird question (assuming not rhetorical), obviously with linear algebra which multivariable calculus relies on.
I am so glad that we are having an AI revolution within mathematics where hopefully the computability crowd will dethrone Cantorianist view.
No, back propagation is just the chain rule from calculus. d(f(g)) = df(g)dg. It is applied to linear algebra, but with linear algebra alone you will never arrive to it.
You can just admit you don't understand calculus (and go and learn it if you care). No reason to go around doing mental gymnastics about it.
[flagged]
Applied calculus doesn't need infinities. No computer can represent a real real number. Only truncations of them, only finite versions of them.
Good luck optimizing without being able to use the condition f'(x) = 0. You might think you can do everything numerically, but when your function has parameters you're in trouble.
Geez, I don't know why I keep arguing with you people. I've seen several examples where just integrating or derivating something gets you an analytic solution that you can compute in an instant, rather than having to start doing some 3 dimension integrals numerically.
https://en.wikipedia.org/wiki/Finite_difference_method
So you're going to always only do numerical computations only? Good luck solving even simple optimization problems that have a few parameters.
I believe finite differences are no less general than derivatives.
Well, the belief is not worth much here. How do you express optimality condition of the form f'(x) = 0 with finite difference? Answer: you don't.
But if this doesn't ring a bell, it's probably better to drop this.
This is another rant about the author's bugaboo.
It would be great to prove that there is or isn't a non-galactic polynomial-time algorithm for NP-complete problems. But we can't even solve the easier problem of proving there is or isn't a galactic polynomial-time algorithm, so what hope is there for the harder problem?
If you could prove that any polynomial-time algorithm for NP problems had to be galactic, you would be the most celebrated computer scientist since Turing. It's just no one has any idea how to do that.
Yep, ranting against galactic polynomial algorithms reminds me of the people who oppose the use of infinity. Like, yes, it's not physically realistic construction, but it makes things simple enough that we can do analytic solutions to problems and simplify terribly complicated things.
Polynomials are closed under multiplication, so you can do a poly algorithms poly number of times and still have a poly algorithm. That's very convenient.
The article makes the point that not all polynomial algorithms are created equal. If you combine ten O(n^2) algorithms, you can end up with an O(n^1024) algorithm, which isn’t practical anymore, despite being polynomial. That’s inconvenient.
I would say it's impractical, but it's actually very convenient for all symbolic manipulation.
I'm a former mathematician and this bit:
> Applied mathematicians often need to build a giant scaffolding of mathematical modeling to solve a problem. This scaffolding creates new mathematical puzzles that aren’t directly connected to the original problem of interest, but that entice problem solvers. You’ll then see dozens of follow-up papers solving the puzzles but forgetting the problem we cared about in the first place.
really resonated with me. The pure math tail is wagging the applied math dog.
Those are two different sets of objectives.
Applied math wants to solve a practical problem. It wants to do something that will actually matter in the real world somewhere.
Pure math wants to understand. It doesn't care about practical application. But we still want it to do well and thrive, because it makes the tools that applied math has available, and when you have a practical problem, that matters.
The point of these "epsilon improvements" is that it challenges people's intuition. It raises the question how much further one can improve on it.
Would be great to get at least a glimpse of an understanding about why the algorithm does the enumeration in the first place.
Surely it cannot be necessary for the complexity result?!
It's just irrelevant for big-O complexity what happens for instances below a constant threshold, so the algorithm uses the simplest approach and moves on. If you have an exponential-time algorithm that's faster than brute force for small instances, you can use that and get a faster overall runtime at the same big-O complexity. If you can lower the switchover threshold, ditto. It's a bit weird to dismiss the subexponential algorithm just because it's leaving an obvious optimization on the table... it can only get faster from here.
This reminds me of the (perhaps unrelated meme) hello I would like (graph of zeta function) number of apples. Statements dreamt up by the utterly deranged.
Indeed I have met professors who claim since something is O(1) it doesn't matter if you run it 4 times. No need to optimize. I think it's just part of the wider divide between theory and application. For instance big O also requires a register machine to make sense, which most courses don't define. Somehow addition and multiplication are O(1) in some places and O(n) or O(n^2) somewhere else. Also quite common is the fact that sets are slower than lists for lookup for small n, despite being O(1).
It's just a tool and we shouldn't miss the trees for the forest. I also understand this comment has nothing to do with the ETH or the article, but just some thoughts I have after reading the first chunk on complexity
Did you ever pause to consider that theoretical computer science might not be done for the sake of midwit code monkeys whose deepest contact with complexity theory was when they learned to reverse a linked list in O(n) for their SWE interview?
Where do you think the money comes from, and why do you think that is?
I'm not sure that retreating to the ivory tower is a winning rhetorical strategy.
Not sure why the hostility anyways. If appreciating TCS results really is a higher brow activity, then GP's indignation at computational models shouldn't upset you, quite the opposite. It's definitionally the normal experience.
And while I do find the blogpost in the OP trite, that is mostly because it's from someone who should absolutely be more intimate with the subject than such "midwitted code monkeys" (aka. normal people) you refer to, yet pretends to feel duped by OAI's results. Quite the different case, and I think is much more worthy of ridicule as a result. They're the high brow who should be appreciating, understanding, yet fail to.
indeed, the purpose of theoretical computer science is as a filtering and ranking mechanism for awarding tenure in universities
> miss the trees for the forest
I think the common expression is to miss the forest (big picture) for the trees (details). But maybe you're playing on words and saying we shouldn't let the big picture (big O notation/analysis) obscure our attention to the details (an algorithm's actual efficiency and performance).
I guess in engineering what you care about is: how fast is it on given input size X relevant for the practical problem. Or: how much input size can we do in time bound Y.
I don't think the author's criticism of "Big-O Cabal" is very nuanced, but to the second half of the essay it is funny/concerning/sobering to find that the OpenAI proof is doing brute-force search for all instances below some super-astronomic threshold. It kind of buries the lede if the proof did not mention this clearly and the author has to comb through it to find out (I asked ChatGPT the same on the pdf file, but it came up with some other threshold number).
I don't think it matters? It's completely standard for "galactic" algorithms and not relevant to big-O runtime.
The complaint that these algorithms aren't "realistic" is ostensibly valid, but you could just as well aim that cannon at 95%+ of math research too. Complexity theory is interesting and fun. Isn't that enough?
> It's completely standard for "galactic" algorithms and not relevant to big-O runtime.
This is true, but if doing brute-force search for all instances below some super-astronomic threshold is part of the algorithm, you typically want to understand
- where this constant comes from,
- how much this constant can be decreased (or why it can't)
- etc.
So, proving the correctness of an algorithm which is doing brute-force search for all instances below some super-astronomic threshold is typically just the first step towards getting an understanding of the complexity-theoretic phenomenon.
So: There is indeed nothing wrong with such aspects of galactic algorithms, but exactly understanding and improving the super-astronomic thresholds involved is the next step.
I hate to use absolutely but it absolutely does matter from an education perspective. To put things in perspective to a layperson explain to them this particular galactic theorem requires full search below some titanic |x|. That should prompt some excellent lay questions that a serious computer scientist ought to reckon with.
It is not to say the approach has been wrong (as the author strongly believes in his reframing) but that this clarity does matter for purposes of, ahem, mathematical understanding.
Post #1,000,037 complaining about AI in math by ragging on the existence of pure math. Sigh.
Time complexity is hardly pure math, there are tons of practical uses in addition to the "purer" parts.
One point of the article is that much of what falls under complexity theory is indeed useless pure math masquerading as useful applied math.
Well, since no one has sided with the author, let the math coin clipping keep going without pause.
[dead]
Author is a math professor who somehow wants you to believe that he didn't know what a computational model is until OpenAI's manuscript dump a few days ago. In this post, he now extends that pretending game to galactic algorithms.
Very gonzo, but maybe I prefer to learn about these things with a little less circlejerk.
[dead]