¿Hay alguna prueba de que la suma es más rápida que la multiplicación?

21

El mejor límite superior conocido en la complejidad temporal de la multiplicación es el límite de Martin Fürer , que es más que la complejidad lineal de tiempo de la suma. ¿Tenemos una prueba de que la suma es inherentemente más fácil que la multiplicación?nlog⁡n2O(log∗⁡n)

cc.complexity-theory time-complexity Hooman
fuente
Corregido el tiempo límite.
Jeffε
1
vea también los principales problemas no resueltos en TCS
vzn
1
dependerá de cómo representes tus números; si manejas el registro del número, la multiplicación es más rápida que la suma (ya que requiere un pow y un registro)
monstruo de trinquete

Respuestas:

30

No.

Actualmente no se conoce un límite inferior incondicional mejor que el trivial ( n ) para la multiplicación de enteros. Sin embargo, hay algunos límites inferiores condicionales. Para obtener más información sobre esto, puede echar un vistazo a la multiplicación entera más rápida en papel de Martin Fürer .Ω(n)

Editar siguiendo el comentario de Andrej: La adición se puede hacer a tiempo . En comparación, el límite superior más conocido para la multiplicación es (aproximadamente) O ( n log n ) . Por otro lado, no se conoce un límite inferior no trivial para la multiplicación, por lo que todavía no hay pruebas de que la suma sea más rápida que la multiplicación. Como (también) a menudo en la teoría de la complejidad, ¡simplemente no lo sabemos!O(n)O(nlog⁡n)

Bruno
fuente
Me parece que el documento no refuta que la suma es más rápida que la multiplicación. ¿Debo suponer que todavía no hay pruebas de eso?
Hooman
8
Lo que Bruno dice es esto: claramente podemos sumar en tiempo lineal, y no podemos hacerlo más rápido que en tiempo lineal (porque hay que mirar la entrada). Por lo tanto, mostrar que la suma es más difícil que la multiplicación es lo mismo que mostrar que la multiplicación no se puede hacer en tiempo lineal. Pero no hay tal prueba.
Andrej Bauer
2
@andrej te refieres a "mostrar la multiplicación es más difícil que la suma" ¿verdad? el póster lo mezcló también en una versión anterior de la pregunta. También objeción, no hay tal prueba conocida . esto también parece ser un buen candidato para el desbordamiento matemático, "los problemas abiertos más 'obvios' en la teoría de la complejidad"
vzn
@vzn es una gran respuesta a esa pregunta de MO, IMO.
Sasho Nikolov
@SashoNikolov No estoy seguro: no sé si la multiplicación en O (n) sería tan impactante. Ciertamente es una sorpresa, pero AFAIK no hay una buena razón, excepto por analogía con problemas como la clasificación, las transformadas de Fourier, etc. para creer que el problema de multiplicación 'naturalmente' O (n ^ 2) no podría simplificarse hasta el tiempo lineal .
Steven Stadnicki