Existe-t-il une preuve que l'addition est plus rapide que la multiplication?

La meilleure borne supérieure connue sur la complexité temporelle de la multiplication est la borne Martin Fürer , qui est plus qu'une complexité temporelle linéaire de l'addition. Avons-nous la preuve que l'addition est intrinsèquement plus facile que la multiplication? $n\log n2^{O(\log^* n)}$

cc.complexity-theory time-complexity Hooman
la source

Correction de la limite de temps.

Jeffε

voir aussi les problèmes majeurs non résolus dans TCS

vzn

cela dépendra de la façon dont vous représentez vos chiffres; si vous traitez avec le journal de la multiplication des nombres est plus rapide que l'addition (car elle nécessite un pow et un journal)

ratchet freak

Réponses:

Non.

$\Omega(n)$

$\mathcal O(n)$ $\mathcal O(n\log n)$

Bruno
la source

Il me semble que le papier ne prouve pas que l'addition est plus rapide que la multiplication. Dois-je supposer qu'il n'y a pas encore de preuve pour cela?

Hooman

Ce que Bruno dit, c'est ceci: il est clair que nous pouvons faire de l'addition en temps linéaire, et nous ne pouvons pas le faire plus rapidement qu'en temps linéaire (car il faut regarder l'entrée). Par conséquent, montrer que l'addition est plus difficile que la multiplication revient à montrer que la multiplication ne peut pas se faire en temps linéaire. Mais il n'y a pas une telle preuve.

Andrej Bauer

@andrej vous voulez dire "montrer que la multiplication est plus difficile que l'addition" n'est-ce pas? l'affiche l'a mélangé aussi sur une version antérieure de la question. aussi chipoter, il n'y a pas une telle preuve connue . cela semble également être un bon candidat pour mathoverflow, "les problèmes ouverts les plus" évidents "dans la théorie de la complexité"

vzn

@vzn, c'est une excellente réponse à cette question du MO, OMI.

Sasho Nikolov

@SashoNikolov Je ne suis pas sûr - je ne sais pas si la multiplication en O (n) serait tout à fait choquante. Certes, une surprise, mais AFAIK il n'y a pas de bonne raison, sauf par analogie avec des problèmes comme le tri, les transformées de Fourier, etc. de croire que le problème de multiplication `` naturellement '' O (n ^ 2) ne pouvait pas être simplifié jusqu'au temps linéaire .

Steven Stadnicki