Gibt es einen Beweis dafür, dass Addition schneller ist als Multiplikation?

21

Die beste bekannte obere Schranke für die zeitliche Komplexität der Multiplikation ist Martin Fürers Schranke , die mehr als die lineare zeitliche Komplexität der Addition ist. Haben wir einen Beweis, dass Addition von Natur aus einfacher ist als Multiplikation?nLog⁡n2O(Log∗⁡n)

cc.complexity-theory time-complexity Hooman
quelle
Zeitbindung korrigiert.
Jeffs
1
siehe auch große ungelöste Probleme in TCS
vzn
1
es wird davon abhängen, wie Sie Ihre Zahlen darstellen; Wenn Sie mit dem Protokoll der Zahlenmultiplikation umgehen, ist diese Addition schneller (da es einen Pow und ein Protokoll erfordert)
Ratschenfreak

Antworten:

30

Nein.

Für die ganzzahlige Multiplikation ist derzeit keine unbedingt bessere Untergrenze als das triviale bekannt. Es gibt jedoch einige bedingte Untergrenzen. Weitere Informationen hierzu finden Sie in Martin Fürers Artikel Faster Integer Multiplication .Ω(n)

Bearbeiten Sie den folgenden Kommentar von Andrej: Die Hinzufügung kann in der Zeit . Im Vergleich dazu ist die bekannteste Obergrenze für die Multiplikation (ungefähr) O ( n log n ) . Andererseits ist keine nicht triviale Untergrenze für die Multiplikation bekannt, so dass es keinen Beweis dafür gibt, dass die Addition noch schneller als die Multiplikation ist. Wie (zu) oft in der Komplexitätstheorie wissen wir es einfach nicht!O(n)O(nLog⁡n)

Bruno
quelle
Es scheint mir, dass das Papier nicht widerlegt, dass die Addition schneller ist als die Multiplikation. Sollte ich davon ausgehen, dass es dafür noch keinen Beweis gibt?
Hooman
8
Was Bruno sagt, ist folgendes: Wir können eindeutig in linearer Zeit addieren und wir können es nicht schneller tun als in linearer Zeit (weil Sie sich die Eingabe ansehen müssen). Zu zeigen, dass Addition schwieriger ist als Multiplikation, ist daher dasselbe wie zu zeigen, dass Multiplikation nicht in linearer Zeit durchgeführt werden kann. Aber es gibt keinen solchen Beweis.
Andrej Bauer
2
@andrej du meinst "Multiplikation ist schwieriger als Addition" oder? Das Plakat hat es auch mit einer früheren Version der Frage verwechselt. auch streiten, gibt es keinen solchen Beweis bekannt . dies scheint auch ein guter kandidat für mathoverflow zu sein, "offensichtlichste" offene probleme in der komplexitätstheorie "
vzn 20.09.12
@vzn es ist eine großartige Antwort auf diese MO-Frage, IMO.
Sasho Nikolov
@SashoNikolov Ich bin nicht sicher - ich weiß nicht, ob die Multiplikation in O (n) so schockierend wäre. Gewiss eine Überraschung, aber AFAIK gibt es keinen guten Grund, außer in Analogie zu Problemen wie Sortieren, Fouriertransformationen usw. zu glauben, dass das "natürliche" O (n ^ 2) -Multiplikationsproblem nicht bis hinunter zur linearen Zeit vereinfacht werden kann .
Steven Stadnicki