1. Upper bounds Let M (n) denote the cost of multiplying n-bit integers.
Statement
- Upper bounds Let M (n) denote the cost of multiplying n-bit integers. By “cost” we mean the number of steps performed by a multitape Turing machine [Pap94]. Theorem 1 ([HvdH21]). M (n) = O(n log n). Suprisingly, the “function field case” appears to be more difficult. For a prime p, let Mp (d) denote the cost (still in the Turing model) of multiplying polynomials in Fp [x] of degree d. Then we have the following folklore conjecture. In this talk I gave an overview of what is known about upper and lower bounds for the complexity of integer multiplication and some related problems.
Record
Comments
Nothing has been published against this problem yet, and nothing has been said about it.
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.