Loading AI tools
Из Википедии, свободной энциклопедии
Гипотеза Штрассена — утверждение о том, что для сколь угодно малого существует алгоритм, при достаточно больших натуральных гарантирующий перемножение двух квадратных матриц размера за операций.
Выдвинута Фолькером Штрассеном в 1969 году; по состоянию на 2023 год остаётся одной из важных нерешенных проблем линейной алгебры и теории сложности вычислений.
Задача перемножения двух больших квадратных матриц часто встречается в приложениях и её ускорение этой операции имеет большое практическое значение. Поскольку при умножении матриц надо вычислить новых, вообще говоря, разных значений элементов матриц, это нельзя сделать менее, чем за операций. Стандартный алгоритм согласно определению умножения матриц требует операций. Алгоритм Штрассена, опубликованный в 1969 году[1], требовал умножений; в той же работе выдвинута гипотеза о возможности перемножать матрицы со скоростью, сколь угодно близкой к .
В 1990 году было доказано, что достаточно операций (алгоритм Копперсмита — Винограда)[2]. Этот алгоритм имеет теоретическое значение и не может использоваться на практике, поскольку реально ускоряет умножение только для астрономически больших матриц. В дальнейшем было получено несколько очень незначительных улучшений последней оценки на базе того же метода[3]. Это позволяет предположить существование «барьера Копперсмита — Винограда» в теоретических оценках сложности этой задачи, хотя большинство исследователей полагает, что гипотеза Штрассена верна. Показатель степени в практических алгоритмах был несколько улучшен по сравнению с показателем алгоритма Штрассена, но пока он остаётся существенно больше показателя алгоритма Копперсмита — Винограда.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.