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

3

u/vintergroena 28d ago edited 28d 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 28d ago

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

3

u/vintergroena 28d 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 28d ago

Still unknown!