Definisi eksponen matriks-perkalian

Bahasa sehari-hari, definisi eksponen matriks-perkalian $\omega$ adalah nilai terkecil yang ada algoritma perkalian-matriks $n^{\omega}$ . Ini tidak dapat diterima sebagai definisi matematika formal, jadi saya kira definisi teknis adalah sesuatu seperti infimum atas semua $t$ seperti bahwa ada algoritma matriks-perkalian dalam $n^t$ .

Dalam hal ini, kita tidak bisa mengatakan ada algoritma untuk perkalian-matriks dalam $n^{\omega}$ atau bahkan $n^{\omega + o(1)}$ , hanya saja untuk semua $\epsilon > 0$ ada algoritma dalam $n^{\omega + \epsilon}$ . Namun, sering kali, makalah dan hasil yang menggunakan perkalian matriks akan melaporkan biayanya hanya sebagai $O(n^{\omega})$ .

Apakah ada beberapa definisi alternatif yang mengizinkan penggunaan ini? Apakah ada hasil yang menjamin bahwa algoritma waktu n ω atau n ω + o ( 1 ) harus ada? Atau apakah penggunaan O ( n ω ) hanya ceroboh?$\omega$$n^{\omega}$$n^{\omega + o(1)}$$O(n^{\omega})$

Eksponen perkalian matriks menjadi tidak menjamin bahwa ada algoritma yang berjalan dalam waktu O ( n ω ) , tetapi hanya untuk setiap ϵ > 0 , ada algoritma yang berjalan di O ( n ω + ϵ ) . Memang jika Anda dapat menemukan algoritma yang berjalan dalam waktu O ( n 2 p o l y l o g ( n ) ) , maka ini menunjukkan bahwa ω = 2 .$\omega$$O(n^\omega)$$\epsilon > 0$$O(n^{\omega+\epsilon})$$O(n^2 \mathrm{polylog}(n))$$\omega = 2$

Anda dapat menemukan definisi formal dalam buku Algebraic Complexity Theory oleh Peter Bürgisser, Michael Clausen, Amin Shokrollahi.

Komentar minor yang terlalu panjang untuk dijadikan komentar:

Kadang-kadang ketika Anda memiliki masalah yang ada algoritma dengan berjalan waktu untuk setiap ε > 0 , ada sebuah algoritma dengan berjalan waktu n k + o ( 1 ) .$O(n^{k+\epsilon})$$\epsilon>0$$n^{k+o(1)}$

Misalnya, terkadang Anda mendapatkan algoritme yang mirip dengan untuk beberapa fungsi yang tumbuh cepat f (seperti 2 2 1 / ϵ ). Jika Anda mengatur f ( 1 / ϵ ) menjadi (katakanlah) log n , maka ϵ akan menjadi o (1). Dalam contoh dengan f ( 1 / ϵ ) menjadi 2 2 1 / ϵ , Anda dapat memilih 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$ menjadi , yang memberikan $\log \log \log n$ , yaitu o (1). Jadi waktu berjalan akhir dari algoritma ini akan n k + o ( 1 ) , karena log n juga n o ( 1 ) .$\epsilon = 1/ (\log \log \log n)$$n^{k+o(1)}$$\log n$$n^{o(1)}$

It is well-known the result of Coppersmith and Winograd that $O(n^{\omega})$-time cannot be realized by any single algorithm. But I've read that they restricted to algorithms based on Strassen-like bilinear identities, so I don't know for sure since the paper is behind a paywall.

I do not agree with your statement in the question that $\omega$ is not well-defined by "the smallest value for which there is a known $n^ω$ matrix-multiplication algorithm." When people are using this constant, it is because their algorithm relies on a matrix multiplication, and by a complexity $n^\omega$, they mean "the optimal complexity of our algorithm is given by the optimal algorithm for matrix multiplication."

I am not saying that it is not possible to define $\omega$ otherwise (e.g. saying that $\omega$ is the best achievable complexity).

Btw, the best known upper bound for matrix multiplication has just been improved to $2.3737$ if I am not mistaken.