Гипотеза Штрассена

Материал из Википедии — свободной энциклопедии

В теории алгоритмов и линейной алгебре гипотеза Штрассена утверждает, что для любой заданной скорости (до определённого предела) существует алгоритм, позволяющий перемножать достаточно большие матрицы с такой скоростью. Были найдены достаточно быстрые алгоритмы, но в общем случае задача не решена до сих пор.

[править] Точная формулировка

Для сколь угодно малого $\varepsilon > 0$ существует алгоритм, при достаточно больших натуральных n гарантирующий перемножение двух матриц размера $n \times n$ за ${\rm O}(n^{2+\varepsilon})$ операций.

[править] История

Задача перемножения двух больших квадратных матриц часто встречается на практике — этим объясняется практическая ценность гипотезы. Поскольку умножение чисел есть операция более трудоёмкая, чем сложение, то при оценке сложности алгоритма перемножения матриц учитывают только количество умножений. Очевидно, что две матрицы размера $n \times n$ можно перемножить за n³ умножений и n²(n-1) сложений; очевидно также, что нельзя сделать степень n меньше 2 (т.к. в таких матрицах n² значений, и все их надо обработать). Однако хотелось бы сократить количество производимых умножений (возможно, за счёт увеличения количества сложений). В 1969 году немецкий учёный Штрассен предложил более быстрый алгоритм, который требовал ${\rm O}(n^{\log_2 7}) \approx {\rm O}(n^{2,807})$ умножений. В 1982 году было доказано, что достаточно $O(n 2,376)$ операций (алгоритм Копперсмита—Винограда), хотя предложенный ими алгоритм редко используется на практике и имеет скорее теоретическое значение.