O36 — Integer multiplication in linear bit complexity
Can two positive integers be multiplied using bit operations?
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 solution
GitHub repository: https://github.com/openai/math
- OpenAI-109-01-Integer-multiplication-below-n-log-n.pdfOpen