Гипотеза Штрассена | это... Что такое Гипотеза Штрассена? (original) (raw)
В теории сложности вычислений и линейной алгебре гипотеза Штрассена утверждает, что для любой заданной скорости (до определённого предела) существует алгоритм, позволяющий перемножать достаточно большие матрицы с такой скоростью. Были найдены достаточно быстрые алгоритмы, но в общем случае задача не решена до сих пор.
Точная формулировка
Для сколь угодно малого 
существует алгоритм, при достаточно больших натуральных n гарантирующий перемножение двух матриц размера 
за 
операций.
История
Задача перемножения двух больших квадратных матриц часто встречается на практике — этим объясняется практическая ценность гипотезы. Поскольку умножение чисел есть операция более трудоёмкая, чем сложение, то при оценке сложности алгоритма перемножения матриц учитывают только количество умножений. Очевидно, что две матрицы размера можно перемножить за n³ умножений и n²(n-1) сложений; очевидно также, что нельзя сделать степень n меньше 2 (так как в таких матрицах n² значений, и все их надо обработать). Однако хотелось бы сократить количество производимых умножений (возможно, за счёт увеличения количества сложений). В 1969 году немецкий учёный Штрассен предложил более быстрый алгоритм, который требовал 
умножений. В 1982 году было доказано, что достаточно 
операций (алгоритм Копперсмита — Винограда), хотя предложенный ими алгоритм редко используется на практике и имеет скорее теоретическое значение.