Definicja wykładnika mnożenia macierzy

Potocznie definicja wykładnika mnożenia macierzy jest najmniejszą wartością, dla której znany jest algorytm mnożenia macierzy . Nie jest to dopuszczalne, formalnej definicji matematycznej tak Chyba określenie techniczne jest czymś w infimum na wszystkich tak, że istnieje algorytm mnożenia macierzy w .n ω t n $\omega$$n^{\omega}$$t$$n^t$

W tym przypadku nie możemy powiedzieć, że istnieje algorytm mnożenia macierzy w lub nawet , po prostu że dla wszystkich istnieje algorytm w . Często jednak artykuły i wyniki wykorzystujące mnożenie macierzy podają swój koszt jako po prostu . n ω + o ( 1 ) ϵ > 0 n ω + ϵ O ( n ω$n^{\omega}$$n^{\omega + o(1)}$$\epsilon > 0$$n^{\omega + \epsilon}$$O(n^{\omega})$

Czy istnieje jakaś alternatywna definicja która pozwala na to użycie? Czy są jakieś wyniki, które gwarantują, że musi istnieć algorytm czasu lub ? A może użycie po prostu niechlujne?n ω n ω + o ( 1 ) O ( n ω$\omega$$n^{\omega}$$n^{\omega + o(1)}$$O(n^{\omega})$

Wykładnik mnożenia macierzy będący nie gwarantuje, że istnieje algorytm działający w czasie , ale tylko, że dla każdego istnieje algorytm działający w . Rzeczywiście, jeśli możesz znaleźć algorytm działający w czasie , oznacza to, że .O ( n ω ) ϵ > 0 O ( n ω + ϵ ) O ( n 2 p o l y l o g ( n ) ) ω = $\omega$$O(n^\omega)$$\epsilon > 0$$O(n^{\omega+\epsilon})$$O(n^2 \mathrm{polylog}(n))$$\omega = 2$

Formalną definicję można znaleźć w książce Teoria złożoności algebraicznej autorstwa Petera Bürgissera, Michaela Clausena, Amina Shokrollahi.

Drobny komentarz, który jest zbyt długi, aby być komentarzem:

Czasami, gdy masz problem, dla którego istnieje algorytm z czasem działania dla każdego ϵ > 0 , istnieje algorytm z czasem działania n k + o ( 1 ) .$O(n^{k+\epsilon})$$\epsilon>0$$n^{k+o(1)}$

Na przykład czasami otrzymujesz algorytmy, które działają jak dla niektórych szybko rosnących funkcji f (jak 2 2 1 / ϵ ). Jeśli ustawisz f ( 1 / ϵ ) na (powiedzmy) log n , to ϵ będzie o (1). W przykładzie, w którym f ( 1 / ϵ ) wynosi 2 2 1 / ϵ , możesz wybrać 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$być , co daje ϵ = 1 / ( log log log n ) , co oznacza o (1). Tak więc końcowy czas działania tego algorytmu będzie wynosił n k + o ( 1 ) , ponieważ log n jest również n o ( 1 ) .$\log \log \log n$$\epsilon = 1/ (\log \log \log n)$$n^{k+o(1)}$$\log n$$n^{o(1)}$

Jest dobrze znany wynik Coppersmitha i Winograda, że ​​czas nie może być zrealizowany przez żaden pojedynczy algorytm. Ale przeczytałem , że ograniczają się do algorytmów opartych na dwubiegunowych tożsamościach podobnych do Strassena, więc nie wiem na pewno, ponieważ papier jest za zaporą.$O(n^{\omega})$

Nie zgadzam się z twoim stwierdzeniem w pytaniu, że nie jest dobrze zdefiniowane przez „najmniejszą wartość, dla której istnieje znany algorytm mnożenia macierzy n ω ”. Gdy ludzie używają tej stałej, dzieje się tak dlatego, że ich algorytm opiera się na mnożeniu macierzy, a przez złożoność n ω , mają na myśli „optymalną złożoność naszego algorytmu zapewnia optymalny algorytm mnożenia macierzy”.$\omega$$n^ω$$n^\omega$

Nie twierdzę, że inaczej nie można zdefiniować (np. Twierdzenie, że ω jest najlepszą możliwą do osiągnięcia złożonością).$\omega$$\omega$

Btw, najbardziej znana górna granica mnożenia macierzy została właśnie poprawiona do jeśli się nie mylę. $2.3737$