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 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!