← All problems

O36 — Integer multiplication in linear bit complexity

Can two positive integers a,ba,b be multiplied using O(log⁡(ab))O(\log(ab)) bit operations?

References

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 1

Claimed by OpenAI. The manuscript claims multiplication of all n-bit integer inputs in worst-case O(n*(log n)^(1-2^-182)) time on a fixed deterministic finite-alphabet multitape Turing machine. This is related progress toward the page’s linear bit-complexity question, with a superlinear bound and potentially enormous constants; it does not claim O(n) time or a practical implementation.See full solutionHide full solution