Czy istnieje dowód, że dodawanie jest szybsze niż mnożenie?

21

Najlepszą znaną górną granicą złożoności czasowej mnożenia jest granica Martina Fürera ( log ∗ n ) , która jest więcej niż liniowa złożoność czasowa dodawania. Czy mamy dowód, że dodawanie jest z natury łatwiejsze niż mnożenie?nlog⁡n2)O(log∗⁡n)

cc.complexity-theory time-complexity Hooman
źródło
Poprawiono limit czasu.
Jeffε
1
patrz także główne nierozwiązane problemy w TCS
wer 20'12
1
będzie to zależeć od tego, jak reprezentujesz swoje liczby; jeśli masz do czynienia z logarytmem mnożenia liczb, jest to szybsze niż dodawanie (ponieważ wymaga pow i logu)
maniak zapadkowy

Odpowiedzi:

30

Nie.

Żadne bezwarunkowe lepsze dolne ograniczenie niż trywialne jest obecnie znane z mnożenia liczb całkowitych. Istnieją jednak pewne warunkowe dolne granice. Więcej informacji na ten temat można znaleźć w artykule Martina Fürera Faster Integer Multiplication .Ω(n)

Edytuj następujący komentarz Andreja: Dodawanie można wykonać w czasie . Dla porównania, najbardziej znaną górną granicą mnożenia jest (w przybliżeniu) . Z drugiej strony, żadna nietrywialna dolna granica nie jest znana z mnożenia, dlatego nie ma dowodów na to, że dodawanie jest jeszcze szybsze niż mnożenie. Jak (często) w teorii złożoności, po prostu nie wiemy!O ( n log n )O(n)O(nlog⁡n)

Bruno
źródło
Wydaje mi się, że praca nie obala, że ​​dodawanie jest szybsze niż mnożenie. Czy powinienem założyć, że nie ma na to jeszcze dowodów?
Hooman
8
Bruno mówi tak: wyraźnie możemy dodawać w czasie liniowym i nie możemy tego robić szybciej niż w czasie liniowym (ponieważ trzeba spojrzeć na dane wejściowe). Dlatego pokazanie, że dodawanie jest trudniejsze niż mnożenie, jest tym samym, co pokazanie, że mnożenia nie można wykonać w czasie liniowym. Ale nie ma takiego dowodu.
Andrej Bauer,
2
@ andrej masz na myśli „pokazanie mnożenia jest trudniejsze niż dodawanie”, prawda? plakat pomieszał go także z wcześniejszą wersją pytania. również zastrzeżenie, nie ma takiego dowodu znane . to również wydaje się dobrym kandydatem na mathoverflow, „większość«oczywiste»otwartych problemów w teorii złożoności”
vzn
@vzn to świetna odpowiedź na to pytanie MO, IMO.
Sasho Nikolov
@SashoNikolov Nie jestem pewien - nie wiem, czy mnożenie w O (n) byłoby tak szokujące. Z pewnością niespodzianka, ale AFAIK nie ma żadnego dobrego powodu, z wyjątkiem analogii z problemami takimi jak sortowanie, transformaty Fouriera itp., Aby sądzić, że problemu „naturalnego” mnożenia O (n ^ 2) nie można uprościć aż do czasu liniowego .
Steven Stadnicki