Dowody na to, że mnożenie macierzy można przeprowadzić w czasie kwadratowym?

Powszechnie przypuszcza się, że , optymalny wykładnik mnożenia macierzy, w rzeczywistości jest równy 2. Moje pytanie jest proste:$\omega$

Jakie mamy powody, by sądzić, że ?$\omega = 2$

Mam świadomość szybkich algorytmów, takich jak Coppersmith-Winograd, ale nie wiem, dlaczego można je uznać za dowód na .$\omega = 2$

Naiwnie wydaje mi się, że jest to klasyczny przykład, w którym społeczność ma tylko nadzieję, że wynik jest prawdziwy wyłącznie ze względów estetycznych. Chciałbym wiedzieć, czy tak jest w istocie w tym przypadku.

$\frac{3}{2^{2/3}}$$\frac{3}{2^{2/3}}$

(W przypadku ich innych hipotez 4.7, które są teorią grupową, nie znam żadnych podobnych dowodów wiarygodności poza intuicją.)

Po drugie, zgadzam się z Amirem Shpilką, że ciąg przeszłych algorytmów ma nieco ad hoc charakter. Jedną z miłych rzeczy w podejściu grupowym jest to, że prawie wszystkie (nie całkiem) poprzednie algorytmy można sformułować w tym podejściu. Chociaż różne konstrukcje teoretyczne w grupach w [CKSU] mogą wydawać się nieco doraźne na zewnątrz, w kontekście ram teoretycznych grup wydają się znacznie bardziej naturalne i mniej ad-hoc (przynajmniej dla mnie) niż wiele innych poprzednie algorytmy.

$\omega=2$$\omega=2$

$\omega = 2$

$A$$B$$n$$n$$C = AB$$C(i,j) = \sum_{k=1}^n A(i,k) B(k,j)$$A$$B$$n$$C = A*B$$C(i) = \sum_{k=1}^n A(k)B(i-k)$$\tilde{O}(n)$$O(n^2)$$\tilde{O}(n^2)$algorytm czasowy mnożenia macierzy. Pytanie brzmi: jaki jest analog transformacji Fouriera, który może pomóc w mnożeniu macierzy?

$O(n^{2} log(n^2))$$\omega = 2$