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

Najlepszą znaną górną granicą złożoności czasowej mnożenia jest granica Martina Fürera , 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? $n\log n2^{O(\log^* n)}$

cc.complexity-theory time-complexity

— Hooman
źródło

Poprawiono limit czasu.

— Jeffε

patrz także główne nierozwiązane problemy w TCS

— wer 20'12

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

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 . $\Omega(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! $\mathcal O(n)$ $\mathcal O(n\log 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

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,

@ 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