Integer multiplication is at least as hard as matrix transposition
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866916665768280064 |
|---|---|
| author | Harvey, David van der Hoeven, Joris |
| author_facet | Harvey, David van der Hoeven, Joris |
| contents | Working in the multitape Turing model, we show how to reduce the problem of matrix transposition to the problem of integer multiplication. If transposing an $n \times n$ binary matrix requires $Ω(n^2 \log n)$ steps on a Turing machine, then our reduction implies that multiplying $n$-bit integers requires $Ω(n \log n)$ steps. In other words, if matrix transposition is as hard as expected, then integer multiplication is also as hard as expected. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_22848 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Integer multiplication is at least as hard as matrix transposition Harvey, David van der Hoeven, Joris Computational Complexity Symbolic Computation Primary 68Q17, Secondary 68W30 Working in the multitape Turing model, we show how to reduce the problem of matrix transposition to the problem of integer multiplication. If transposing an $n \times n$ binary matrix requires $Ω(n^2 \log n)$ steps on a Turing machine, then our reduction implies that multiplying $n$-bit integers requires $Ω(n \log n)$ steps. In other words, if matrix transposition is as hard as expected, then integer multiplication is also as hard as expected. |
| title | Integer multiplication is at least as hard as matrix transposition |
| topic | Computational Complexity Symbolic Computation Primary 68Q17, Secondary 68W30 |
| url | https://arxiv.org/abs/2503.22848 |