Есть ли доказательство того, что сложение происходит быстрее, чем умножение?

Лучшая известная верхняя граница для временной сложности умножения - это оценка Мартина Фюрера , которая является более чем линейной сложностью сложения по времени. Есть ли у нас доказательство того, что сложение по сути проще, чем умножение? $n\log n2^{O(\log^* n)}$

cc.complexity-theory time-complexity Hooman
источник

Исправлено время.

Джеффс

см. также основные нерешенные проблемы в TCS

vzn

это будет зависеть от того, как вы представляете свои числа; если вы имеете дело с журналом умножения чисел, это быстрее, чем сложение (так как для него требуется логарифм и лог)

трещотка урод

Нет.

Никакая безусловная лучшая нижняя граница, чем тривиальное в настоящее время не известна для умножения целых чисел. Однако есть некоторые условные нижние границы. Подробнее об этом вы можете узнать из статьи Мартина Фюрера « Быстрое целочисленное умножение» . $\Omega(n)$

Редактируйте после комментария Андрея: Добавление может быть сделано за время . Для сравнения, самая известная верхняя граница умножения равна (приблизительно) . С другой стороны, нет нетривиальной нижней границы для умножения, поэтому нет никаких доказательств того, что сложение еще быстрее, чем умножение. Как (слишком) часто в теории сложности, мы просто не знаем! $\mathcal O(n)$ $\mathcal O(n\log n)$

Bruno
источник

Мне кажется, что в статье не опровергается, что сложение происходит быстрее, чем умножение. Должен ли я предположить, что пока нет доказательств этого?

Хуман

Бруно говорит следующее: ясно, что мы можем делать сложение в линейном времени, и мы не можем делать это быстрее, чем в линейном времени (потому что вы должны смотреть на вход). Следовательно, показать, что сложение сложнее, чем умножение, - это то же самое, что показать, что умножение невозможно выполнить за линейное время. Но таких доказательств нет.

Андрей Бауэр

@andrej, ты имеешь в виду "показывать умножение сложнее, чем сложение", верно? постер перепутал также более раннюю версию вопроса. Кроме того, нет никаких доказательств, известных . это также кажется хорошим кандидатом для mathoverflow, «наиболее« очевидных »открытых проблем в теории сложности»

vzn

@vzn - отличный ответ на этот вопрос МО, ИМО.

Сашо Николов

@SashoNikolov Я не уверен - я не знаю, было бы шокирующим умножение в O (n). Конечно, сюрприз, но у AFAIK нет веской причины, кроме как по аналогии с такими проблемами, как сортировка, преобразования Фурье и т. Д., Полагать, что «естественно» задача умножения O (n ^ 2) не может быть упрощена вплоть до линейного времени. ,

Стивен Стадницки

Есть ли доказательство того, что сложение происходит быстрее, чем умножение?

Ответы:

Нет.