Определение показателя умножения матриц

В разговорной речи определение показателя умножения матриц является наименьшим значением, для которого существует известный алгоритм умножения матриц . Это неприемлемо как формальное математическое определение, поэтому я предполагаю, что техническое определение является чем-то вроде инфимума по всем , так что в существует алгоритм умножения матриц .$\omega$$n^{\omega}$$t$$n^t$

В этом случае нельзя сказать, что существует алгоритм умножения матриц в или даже в , просто для всех существует алгоритм в . Однако, часто статьи и результаты, которые используют умножение матриц, сообщают о своей стоимости просто как .$n^{\omega}$$n^{\omega + o(1)}$$\epsilon > 0$$n^{\omega + \epsilon}$$O(n^{\omega})$

Есть ли какое-то альтернативное определение которое разрешает такое использование? Существуют ли какие-либо результаты, гарантирующие, что алгоритм времени или должен существовать? Или использование просто небрежно?п ω п ω + O ( 1 ) О ( п ω$\omega$$n^{\omega}$$n^{\omega + o(1)}$$O(n^{\omega})$

Показатель умножения матриц, являющийся , не гарантирует, что существует алгоритм, который выполняется за время O ( n ω ) , но только то, что для каждого ϵ > 0 , существует алгоритм, который выполняется за O ( n ω + ϵ ) . Действительно , если вы можете найти алгоритм , который работает в время O ( п 2 р о л у л о г ( п ) ) , то это показывает , что ω = 2 .$\omega$$O(n^\omega)$$\epsilon > 0$$O(n^{\omega+\epsilon})$$O(n^2 \mathrm{polylog}(n))$$\omega = 2$

Вы можете найти формальное определение в книге «Теория алгебраической сложности» Питера Бюргиссера, Михаэля Клаузена, Амина Шокроллахи.

Небольшой комментарий, который слишком длинный, чтобы быть комментарием:

Иногда, когда у вас есть проблема, для которой существует алгоритм со временем выполнения для каждого ϵ > 0 , существует алгоритм со временем выполнения n k + o ( 1 ) .$O(n^{k+\epsilon})$$\epsilon>0$$n^{k+o(1)}$

Например, иногда вы получаете алгоритмы, которые идут как для некоторой быстро растущей функции f (например, 2 2 1 / ϵ ). Если вы установите f ( 1 / ϵ ) в (скажем) log n , то ϵ будет o (1). В примере с f ( 1 / ϵ ), равным 2 2 1 / ϵ , вы можете выбрать 1 /$f(1/\epsilon)n^{k+\epsilon}$$f$$2^{2^{1/\epsilon}}$$f(1/\epsilon)$$\log n$$\epsilon$$f(1/\epsilon)$$2^{2^{1/\epsilon}}$$1/\epsilon$быть , что дает ϵ = 1 / ( log log log n ) , что равно o (1). Таким образом, окончательное время работы этого алгоритма будет n k + o ( 1 ) , поскольку log n также равно n o ( 1 ) .$\log \log \log n$$\epsilon = 1/ (\log \log \log n)$$n^{k+o(1)}$$\log n$$n^{o(1)}$

Хорошо известен результат Копперсмита и Винограда о том, что -время не может быть реализовано ни одним единственным алгоритмом. Но я читал, что они ограничены алгоритмами, основанными на билинейных тождествах, подобных Штрассену, так что я не знаю точно, так как статья находится за платным доступом.$O(n^{\omega})$

Я не согласен с вашим утверждением в вопросе о том, что недостаточно четко определено «наименьшим значением, для которого существует известный алгоритм умножения матриц n ω ». Когда люди используют эту константу, это потому, что их алгоритм основан на умножении матриц, а под сложностью n ω они подразумевают «оптимальная сложность нашего алгоритма определяется оптимальным алгоритмом умножения матриц».$\omega$$n^ω$$n^\omega$

Я не говорю, что иначе невозможно определить (например, говоря, что ω - это наилучшая достижимая сложность).$\omega$$\omega$

Кстати, самая известная верхняя граница для умножения матриц только что была улучшена до если я не ошибаюсь. $2.3737$