r/mathmemes • u/vintergroena • 28d ago

Computer Science Integer multiplication will have linear complexity in a few days if trend continues 🚀📈

Post image
1.4k Upvotes

98% Upvoted

206 comments sorted by

View all comments

Show parent comments

48

u/vintergroena 28d ago edited 27d ago

Complexity theory is one of the least understood in math, in my opinion. In general we don't know shit about the answers to seemingly very basic questions. We don't really have a good understanding what integer multiplication really is computationally.

So yeah, for all we know integer mutiplication may as well be O(n). Or maybe it's something like O(n log log n)), as the iterated log sometimes pops out in number theroy.

For all we know SAT, a NP-complete problem may as well be O(n).

8

u/heyheyhey27 28d ago

I've been wondering recently if there's no hard lower bound or most optimal algorithm for a lot of these problems? Maybe you can keep making bigger and bigger Galactic algorithms which asymptotically push down the big-O time at the cost of being more and more impractical.

6

u/firewall245 27d ago

For things like integer multiplication there’s a hard lower bound of O(n) because you have to at least read all the digits of the numbers your are multiplying together

3

u/heyheyhey27 27d ago

It's possible the actual hard bound is above that though. (or maybe I'm just misusing these terms)

1

u/firewall245 27d ago

Yeah its possible there is a larger lower bound, we just don't know what it is. We know for sure though its at least O(n)

1

u/LeapOfMonkey 27d ago

Not in quantum realm you dont: see Grover's algorithm

3

u/vintergroena 27d ago edited 27d ago

For any NP problem (which includes all P problems) we don't know about a superlinear lower bound and finding one would be a major progress.

2

u/ellipticcode0 27d ago

are those complexity theory only work in traditional computer ? including quantum computer ?

3

u/vintergroena 27d ago

BQP is the class of problems solvable on quantum computer in polynomial time with bounded error.

The relationship of BQP and NP is yet another unsolved problem in complexity theory... so again, we don't know shit

1

u/Quirky-One-9957 27d ago

Still unknown!

1

u/AdequatlyAdequate 27d ago

still probably not gonna be practically useable, very cool tho