Multiplicar es una de las operaciones básicas de la informática, presente en el cifrado, la robótica, la inteligencia artificial y el procesamiento de audio. Sin embargo, los matemáticos aún no conocen el método más rápido para hacerlo, un problema con consecuencias económicas globales.
El algoritmo que se enseña en la escuela primaria tiene una complejidad de O(n²): si los números se duplican en longitud, el trabajo computacional se cuadruplica. Multiplicar dos números de mil dígitos requiere un millón de multiplicaciones de un solo dígito. Durante milenios se creyó que O(n²) era un límite imposible de superar.
En 1960, el matemático soviético Andréi Kolmogorov planteó formalmente esta conjetura en un seminario en la Universidad Estatal de Moscú. Una semana después, Anatoli Karatsuba, un estudiante de 23 años, lo desmintió. Karatsuba descubrió que se pueden sustituir multiplicaciones costosas por sumas baratas: mediante un truco algebraico, reemplazó las cuatro multiplicaciones necesarias para multiplicar dos números de dos dígitos por solo tres, y al aplicar este intercambio de forma recursiva logró una complejidad de aproximadamente O(n^1,585).
Desde entonces se han encontrado algoritmos aún más rápidos, pero ninguno ha demostrado ser el óptimo. Encontrar la cota inferior definitiva, es decir, el menor número posible de pasos para multiplicar dos números, sigue siendo un problema abierto en la informática teórica.