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

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

Точная формулировка

Для сколь угодно малого $\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 году было доказано, что достаточно ${\rm O}(n^{2,376})$ операций (алгоритм Копперсмита — Винограда), хотя предложенный ими алгоритм редко используется на практике и имеет скорее теоретическое значение.

См. также

• Алгоритм Штрассена

Для улучшения этой статьи желательно?: Найти и оформить в виде сносок ссылки на авторитетные источники, подтверждающие написанное. Проставить интервики в рамках проекта Интервики.