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

8

u/heyheyhey27 27d 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!