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

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

Выдвинута Фолькером Штрассеном в 1969 году; по состоянию на 2023 год остаётся одной из важных нерешенных проблем линейной алгебры и теории сложности вычислений.

Задача перемножения двух больших квадратных матриц часто встречается в приложениях и её ускорение этой операции имеет большое практическое значение. Поскольку при умножении матриц надо вычислить $n^2$$n^{2}$ новых, вообще говоря, разных значений элементов матриц, это нельзя сделать менее, чем за $O(n^2)$$O(n^{2})$ операций. Стандартный алгоритм согласно определению умножения матриц требует $O(n^3)$$O(n^{3})$ операций. Алгоритм Штрассена, опубликованный в 1969 году, требовал $O(n^{{\log }_2<!--\; \; -->7})\approx <!--\; \approx \; -->O(n^{2,81})$${O}(n^{{\log _{2}7}})\approx {O}(n^{{2,81}})$ умножений; в той же работе выдвинута гипотеза о возможности перемножать матрицы со скоростью, сколь угодно близкой к $O(n^2)$$O(n^{2})$.

В 1990 году было доказано, что достаточно $O(n^{2,376})$${O}(n^{{2,376}})$ операций (алгоритм Копперсмита — Винограда). Этот алгоритм имеет теоретическое значение и не может использоваться на практике, поскольку реально ускоряет умножение только для астрономически больших матриц. В дальнейшем было получено несколько очень незначительных улучшений последней оценки на базе того же метода. Это позволяет предположить существование «барьера Копперсмита — Винограда» в теоретических оценках сложности этой задачи, хотя большинство исследователей полагает, что гипотеза Штрассена верна. Показатель степени в практических алгоритмах был несколько улучшен по сравнению с показателем алгоритма Штрассена, но пока он остаётся существенно больше показателя алгоритма Копперсмита — Винограда.

СсылкиПравить

• Strassen V. Gaussian Elimination is not Optimal (англ.) // Numer. Math / F. Brezzi — Springer Science+Business Media, 1969. — Vol. 13, Iss. 4. — P. 354—356. — ISSN 0029-599X; 0945-3245 — doi:10.1007/BF02165411