Powszechnie przypuszcza się, że , optymalny wykładnik mnożenia macierzy, w rzeczywistości jest równy 2. Moje pytanie jest proste:
Jakie mamy powody, by sądzić, że ?
Mam świadomość szybkich algorytmów, takich jak Coppersmith-Winograd, ale nie wiem, dlaczego można je uznać za dowód na .
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.
ds.algorithms
linear-algebra
matrix-product
Steve Flammia
źródło
źródło
Odpowiedzi:
(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.
źródło
źródło
źródło
źródło