Existe uma prova de que a adição é mais rápida que a multiplicação?

21

O melhor limite superior conhecido na complexidade temporal da multiplicação é o limite Martin Fürer n log n 2 O ( log ∗ n ) , que é mais do que a complexidade de adição linear no tempo. Temos uma prova de que a adição é inerentemente mais fácil que a multiplicação?nlog⁡n2O(log∗⁡n)

cc.complexity-theory time-complexity Hooman
fonte
Corrigido o tempo limite.
Jeffε
11
veja também os principais problemas não resolvidos no TCS
vzn 20/09/2012
11
vai depender de como você representa seus números; se você lidar com o registro do número multiplicação é mais rápido do que a adição (uma vez que requer um prisioneiro de guerra e um log)
aberração catraca

Respostas:

30

Não.

Atualmente, nenhum limite inferior melhor incondicional do que o trivial é atualmente conhecido para multiplicação inteira. Existem alguns limites inferiores condicionais. Para mais informações, você pode dar uma olhada no artigo de Martin Fürer, Multiplicação mais rápida de números inteiros .Ω(n)

Edite a seguir ao comentário de Andrej: A adição pode ser feita no tempo . Em comparação, o limite superior mais conhecido para multiplicação é (aproximadamente) O ( n log n ) . Por outro lado, nenhum limite inferior não trivial é conhecido para multiplicação, portanto, não há prova de que a adição seja mais rápida que a multiplicação. Como (também) frequentemente na teoria da complexidade, simplesmente não sabemos!O(n)O(nlog⁡n)

Bruno
fonte
Parece-me que o artigo não prova que a adição é mais rápida que a multiplicação. Devo assumir que ainda não há provas disso?
Hooman 20/09/12
8
O que Bruno está dizendo é o seguinte: é claro que podemos fazer acréscimos no tempo linear e não podemos fazê-lo mais rapidamente do que no tempo linear (porque você precisa observar a entrada). Portanto, mostrar que a adição é mais difícil que a multiplicação é o mesmo que mostrar que a multiplicação não pode ser feita em tempo linear. Mas não existe essa prova.
Andrej Bauer
2
@andrej, você quer dizer "mostrar multiplicação é mais difícil que adição", certo? o pôster confundiu também uma versão anterior da pergunta. Além disso, não há tal prova conhecida . isso também parece ser um bom candidato para mathoverflow, "a maioria dos problemas 'óbvio' abertos em teoria da complexidade"
vzn
@vzn é uma ótima resposta para essa pergunta do MO, IMO.
Sasho Nikolov 21/09/12
@SashoNikolov Não tenho certeza - não sei se a multiplicação em O (n) seria tão chocante. Certamente é uma surpresa, mas o AFAIK não existe uma boa razão, exceto por analogia com problemas como classificação, transformadas de Fourier, etc., para acreditar que o problema de multiplicação 'natural' de O (n ^ 2) não pode ser simplificado até o tempo linear .
Steven Stadnicki